来自追忆和摩卡串最高赞题解用户教学的传送题解

· · 题解

固定 y 为根，注意到决策的类型只与深度相关，并且决策为「走到父亲」的深度是一段前缀 [1,k]。设有 a_i 个点的深度为 i，深度 i 的点最小期望为 f_i，则

\begin{cases} i & 0 \le i \le k \\ \sum_{i \ge 0} \frac {a_i} {n} f_i & k > i \\ \end{cases}

令 w_k = \sum_{i \ge 0} \frac{a_i} {n} f_i，整理得 w_k = \frac{n + \sum_{0 \le i \le k} i a_i} {\sum_{0 \le i \le k} a_i}。深度 i 的点答案是所有 k 的 f_i 取 \min，即 i 或 w_k 的前缀 \min。直接写 O(n^2 + q) 的做法可以获得 45 分。

容易发现 w_k 是关于 k 单谷的（打表或证明都是容易的），二分最低点位置，快速求出单点值是一个静态树上邻域数点，考虑点分树即可，有 O(n \log^2 n + q) 的做法，q 上不带 \log n 的原因是选不到 \min w_k 时深度就是最优的。这个可以获得 [80, 100] 分，取决于你的卡常水平，我获得了左边界。

https://qoj.ac/submission/2676729

以上是我的考场做法，以下是 @yuanruiqi 场外教我的。

存在一些更好的性质：对于树上相邻的两个点 (u,v)，w_k 最低点的位置最多相差 1。这是因为我们可以在 u 为根的最优策略上通过多走一步来得到 v 的策略，也就是 w_{v,k+1} \le w_{u,k} + 1。先二分一个点，扩展到相邻点只需要进行 O(1) 次 check，复杂度做到 O(n \log n + q)。

https://qoj.ac/submission/2676775