题解：P17141 [NOI 2026] 传送（暂无数据）

vectorwyx · 2026-07-24 20:12:32 · 题解

首先考虑对于一组询问 a,b 如何求出答案 f(a,b)。

记 E=\frac{\sum f(i,b)}{n}，即树上所有点到 b 的期望最少步数的期望，显然有：

其中 d(a,b) 表示树上 a 到 b 的简单路径的边数。但是我们并不知道 E 的具体值，考虑构造辅助函数 g(x)=x-\frac{1}{n}\sum_i \min(d(i,b),1+x)，它有两条性质：g(E)=0，且 g 是单调递增函数（考虑到函数 h(x)=\min(k,1+x) 的导数只可能有 0,1 两种取值，实际上，g'(x) 也是单调的）。

于是问题变为求 g 的零点，更进一步地，由于 d(i,b) 是整数，所以实际上只需要求出该零点的整数部分（即 \lfloor E \rfloor）。直接二分，问题变为给定 x 求 \sum_i \min(d(i,b),1+x)，这等价于求有多少 i 满足 d(i,b)\le 1+x，且这样的 d(i,b) 的和是多少，这是经典邻域信息，可以用点分树维护，算上外层的二分总复杂度为 O(n\log^2 n + q)。

继续观察性质，注意到对于相邻的两点 b,c，对应的所有点到 b 的期望 E_b 和到 c 的期望 E_c 一定满足 |E_b-E_c|\le 1\implies |\lfloor E_b \rfloor|-\lfloor E_c \rfloor|\le 1，所以如果我们已经求出了 \lfloor E_b \rfloor，再去求 \lfloor E_c \rfloor 时就不需要再二分了，而是可以直接去验证它是否等于 \lfloor E_b \rfloor-1,\lfloor E_b \rfloor,\lfloor E_b \rfloor+1。于是可以 O(n\log n) 一次性求出 E_1,E_2,\cdots,E_n，回答询问 a,b 时只需要求一下 d(a,b)，使用基于 dfs 序的 O(n\log n)-O(1) LCA 即可做到 O(n\log n+q)。