P14637 [NOIP2025] 树的价值 / tree

· · 题解

首先 mex 可以转化为每个点可以往某个祖先贡献 1，并且这个贡献会在更浅的时候被抵消掉（由于其他子树的 mex 比较大）。

所以可以转化为每个点往一个祖先的区间贡献 1，并且每个点的贡献只能来自于同一个儿子和他自己。进一步地，可以看作把这个树进行树链剖分，每个点的贡献是所有祖先的 \max\limits_{v \in pre(u)} dep_v - dep_{top_v}+1，设这个东西是 maxd(u)。

考虑 dp，设 f_{u,i} 为 maxd(u) = i 时 u 子树贡献和的最大值，并且需要保证 u 在这个长度为 i 的链上面。设 g_{u,i} 为 maxd(fa_u) = i 时 u 子树贡献和最大值，可以看作是轻儿子的答案。

对于 f_{u,i}，显然有转移 f_{u,i} = \max\limits_v f_{v,i+1} + \sum\limits_{w\neq v} g_{w,i}。

对于 g_{u,i}，那么所有子树内的点 v，若 dep_v - dep_u + 1 < i，那么这些点必定选 i 最优。否则可以选择一个距离 u 为 i 的点开一个新的到 u 的链，链的贡献为链底的 f_{v,i} 加上链上点的轻儿子的 g_{w,i} 的和，还有链上其他点的贡献（都为 i）。那么可以把这个贡献记为 dp_{v,i}，每次在 u 的时候对每个儿子的每个 i 做个子树加即可，用 bit 维护。转移可以直接暴力枚举子树内的点。时间复杂度 O(nm\log m)，常数小可以通过。

考虑优化子树加的部分，只需要维护每个点向上的 sum_{u,i} = \sum\limits_{v\in pre(u) \land dep_u - dep_v \le t - 2} h_{v,i}，可以对每个 i 在树上维护一个指针，每次移动一步变化量是 O(1) 的，总移动次数显然就是按照 dfs 的顺序移动，为 O(n)。时间复杂度 O(nm)。