比赛：LGR236 Div.2

简单题。

假设有 $x$，对于盛开度 $< x$ 的点的盛开度设为 $-1$，对于 $\ge x$ 的点的盛开度设为 $1$，定义一个点的权值为它到根路径上的点盛开度之和，

那么若一个点的权值 $\ge 0$，则代表该点的美丽值 $\ge x$，

也就是说我们要在树上填 $n-x+1$ 个 $1$，$x-1$ 个 $-1$，使得权值 $\ge 0$ 的点数量尽量多，假设这个数量最大为 $y$，那么 $[1,y]$ 的答案都 $\ge x$，

考虑如何求这个最大数量。发现如果存在儿子是 $1$，父亲是 $-1$，那么把儿子和父亲的 $1,-1$ 交换是一定不劣的。因此得出结论：填 $1$ 的点一定构成包含树根的连通块。

考虑用树形背包求这个东西。如果直接设 $f(u,i)$ 表示以 $u$ 为根的子树中，填 $i$ 个 $1$ 的最大答案，没办法转移。

那么就要考虑利用上面得到的结论。即，如果一个点填 $1$，那么它到根路径上的所有点都填 $1$。那么对于每个点，只需要计算它选了之后，会比它父亲多出几个点即可。把它父亲以及祖先的贡献留到上面计算，就不用担心少算贡献了。

至于如何计算每个点比父亲多出的贡献，也是好计算的。赛时多写了一个 DP，$f(u,i)$ 表示 $u$ 子树内距离 $u$ 为 $i$ 的点的数量。实际上不用这么复杂，可以直接 dfs 一遍预处理。

那么背包状态就是，$g(u,i)$ 表示根到 $fa_u$ 路径上点全部填 $1$，$u$ 子树内选了 $i$ 个点填 $1$ 多出的最大贡献。

设某个区间的污水高度为 $x$，选到这个区间的概率为 $P$，序列一共分成 $i$ 段，能出现该区间的划分方案数为 $Q$，那么它对期望的贡献为：

$O(n^3)$ 就是枚举每个区间，再枚举 $i$。预处理即可优化到 $O(n^2)$。