先将问题转化为计算出 $f_{x, y}$ 表示子树内可以走到的结点数量为 $x$，与这些点相邻的走不到的结点数量为 $y$，那么就可以计算出当前点填 $i$ 的答案为：

$$ \sum_{x, y} f_{x, y} \binom{n - x - y}{i - x} (i - 1)! (n - i)! $$

其中 $\binom{n - x - y}{i - x}$ 表示从不确定和 $i$ 的大小关系的点中，需要选出 $i - x$ 个比 $i$ 小的点。

对于每个点 $u$ 计算 $f_{x, y}$，只需要在 DFS 序上 DP。按照 DFS 序遍历每个结点：

• 令这个结点 $\leq$ 子树根结点权值，那么需要继续考虑该结点的儿子结点，转移到 DFS 序 $+ 1$ 的位置，并令 $x \gets x + 1$；
• 令这个结点 $>$ 子树根结点全职，那么不能再选择该结点的儿子结点，直接转移到该子树中 DFS 序最大的位置，并令 $y \gets y + 1$。

于是计算单点答案做到了 $\mathcal{O}(n^3)$。

注意到如果已经计算出 $u$ 的某个儿子结点 $v$ 的 $f$，那么将 $x$ 平移 $1$ 即可复用这部分信息，只需要再插入其他儿子结点即可。考虑轻重链剖分，对于每一条重链从下往上计算答案，可以证明这样做的总时间复杂度为 $\mathcal{O}(n^3)$。

证明：对于每个结点计算其插入 $f$ 的代价和。插入时只需要转移 DFS 序左侧的 $f$ 值，大小为该子树内 DFS 序的平方。而去除一个重子树后，DFS 序至少减半，所以总复杂度为 $T(n) = \mathcal{O}(n^2) + T(\frac{1}{2} n)$ 得 $T(n) = \mathcal{O}(n^2)$。

最后考虑优化统计答案部分的复杂度。注意到式子中 $(i - 1)! (n - i)!$ 部分只与 $i$ 有关，可以提出来。剩下部分将组合数拆开：

$$ \binom{n - x - y}{i - x} = \binom{n - x - (y + 1)}{i - x} + \binom{n - (x + 1) - y}{i - (x + 1)}. $$

即可以将 $f_{x, y}$ 转移到 $f_{x + 1, y}$ 和 $f_{x, y + 1}$，对答案的贡献保持不变。那么只需要将所有 $f$ 值均转移到边界上，再枚举 $i$ 统计答案，单点计算的时间复杂度就做到了 $\mathcal{O}(n^2)$。

总时间复杂度为 $\mathcal{O}(n^3)$。