菜王的 blog

这也是我能干的出来的题吗。我们记题面中的 $x_u$ 为 $h_u$。

求出 $h_u$ 是一个经典的换根 DP 问题，考虑先求出 $g_u$ 表示以 $1$ 为根时 $u$ 子树内包含 $u$ 的连通块的最大权值，然后再进行换根。

对于 $g$，有转移式 $g_u = a_u + \sum_{v \in son(u)} \max(g_v, 0)$。考虑一种情况合法（这里指 $\forall u, 0 \le h_u \le 1$）的一个必要条件是对于所有的 $1 < u \le n$，都有 $|g_u| \le 1$，且 $0 \le g_1 \le 1$。相应的，如果 $u = 1$，我们称 $g_u$ 的合法区间为 $[0, 1]$，否则为 $[-1, 1]$。

考虑证明，首先由于 $h_1 = g_1$，$0 \le g_1 \le 1$ 是显然的；而对于 $u > 1$，$g_u \le 1$ 是显然的，因为 $g_u \le h_u$；至于 $g_u \ge -1$ 是因为我们有 $h_u = g_u + x \ge 0$，其中 $x$ 是 $u$ 子树外面的那一部分，而显然 $x \le 1$。

我们设 $sum = \sum_{v \in son(u)} \max(g_v, 0)$，那么有 $a_u = g_u - sum$。而无论 $u$ 子树中的 $a$ 如何取，都有 $0 \le sum \le |son(u)|$。可以发现，如果 $g_u$ 在其合法区间中，那么无论 $sum$ 是什么，唯一的使得 $g_u$ 取到当前这个值的 $a_u$（也就是 $g_u - sum$）都在 $[1 - n, 1]$ 的范围中，证明分类讨论一下 $u$ 是否为根即可。这也就相当于：任何一组满足所有 $g_u$ 都在合法区间内的 $g$，都有唯一一组 $a$ 可以得到这样的 $g$。

那么我们只需要考虑 $g$ 即可。写出换根的转移式：$h_v = g_v + \max(h_u - \max(g_v, 0), 0)$，然后分类讨论：

• 若 $g_v \in [-1, -h_u)$：$h_v = h_u + g_v < 0$，不合法。
• 若 $g_v \in [-h_u, 0)$：$h_v = h_u + g_v \ge 0$。
• 若 $g_v \in [0, h_u)$：$h_v = h_u$。
• 若 $g_v \in [h_u, 1]$：$h_v = g_v$。

可以发现第二种情况和第四种情况合起来恰好就是 $h_v$ 取遍 $[0, 1]$ 的情况。考虑直接写出 DP：设 $f_u(x)$ 表示 $h_u = x$ 时，$u$ 子树中的 $h_u$ 乘积的和，那么根据上面分类讨论的结果，有转移式：

$f_u(x) = x \prod_{v \in son(u)} \left(x f_v(x) + \int_0^1 f_v(y) dy\right)$

最后的答案就是 $n^{-n} \int_0^1 f_1(x) dx$。显然 $f_u(x)$ 是一个只和 $x$ 有关的多项式，且其次数为 $\mathcal{O}(sz_u)$ 级别。根据树上背包的结论可以分析出直接暴力卷积和计算积分的时间复杂度就是 $\mathcal{O}(n^2)$，可以通过。

code