题解：P14637 [NOIP2025] 树的价值 / tree（民间数据）

· · 题解

首先有暴力 DP f_{i,j,k} 表示 i 子树内 mex 是 j，还有 k 个点没有钦定他的值是多少时子树内最大贡献和。转移的时候 j 取 \max k 求和，复杂度大概是 \mathcal O(n^4)。

这个 DP 的状态和子树大小有关，但是题给条件是深度的限制，考虑如何向这方面靠拢。考虑 f_{i,j,k} 的 j 是从某个子树的 f_{to,j,x} 取到的。设这个子树为重子树，则可以看成是对树进行一个链剖分。

假设初始所有点的点权都是未定义，然后依此确定每个点的点权并考虑他的贡献。一个点 x 到根的重链如果分为 [a_1,b_1],[a_2,b_2],\dots,[a_k,b_k] 这些段，则这个点的权值可以在某个 b_i 被启用（即把 x 的权值设为此时 b_k 子树内 \text{mex}），这样造成的贡献是，[a_k,b_k] 段内的所有点的 \text{mex} 都会加一。（可以调整证明这个东西是能被取满的，不会出现实际贡献是 [t,b_k](t>a_k) 的情况）

这样可以看出令他在 [a_i,b_i] 长度最长的段内被启用就是最优的。

所以问题转化为，对树进行链剖分，每个点的贡献是他到根路径上，最长的一段重链的长度，希望贡献和最大。这样我们就有了 \mathcal O(nd^2) 的 DP（记录当前根链上最长重链和当前重链长度）。

记录两个同质的东西感觉不是特别有用，所以在这方面继续优化：设 F_{i,j} 表示，i 是重链头，i 上面的最长链是 j，此时最大贡献是多少。G_{i,j} 表示，目前 i 到根路径上最长重链段就是 i 此时的重链段，并且其长度目前就是 j，此时最大贡献是多少。

对于 $F$，首先可以让 $F_{i,j}$ 初值为 $j\times siz_i$。然后剩下的情况就是，$i$ 子树内，一个深度比 $i$ 大 $j$ 的点 $x$。此时取到的是 $\displaystyle G_{x,j}+\sum_{k\in \text{chain}(x,i)}\sum_{(k,to)}F_{to,j}$。容易发现，祖先后代之间的贡献的 $j$ 是固定的，所以贡献点对只有 $\mathcal O(nd)$ 个。 看似直接做完了，但是后面这一坨贡献式子其实不是特别好算。经过尝试后不太能直接 $\mathcal O(nd)$，所以上个树剖。 对于一条重链，先处理所有挂在他上面的所有轻子树的 DP 值，然后算出一整条重链上的 DP 值。维护 $s_{i,j}$ 表示 $i$ 到目前子树根的路径上挂着的所有 $F_{to,j}$ 之和（即转移中右侧的求和），因为已经处理完了子树内的 $s$，所以对 $s$ 的更新只需要考虑子树之间的贡献，类似换根 DP，这容易 dfs 一遍目前重链根的子树来做到 $\mathcal O(d\times siz)$。 更新 $s$ 之后就可以对每个重链上的点 $x$，dfs $x$ 的子树来更新 $F_x$。每个点对 $x$ 的贡献是唯一的，贡献式中右侧的求和符号可以用已经处理好的 $s$ 差分得到，所以转移是 $\mathcal O(1)$ 的。 分析复杂度：第一部分更新 $s$ 的复杂度是 $\mathcal O(nd\log n)$（因为轻子树和是 $\mathcal O(n\log n)$），第二部分更新 $F$ 是子树大小和，即 $\mathcal O(nd)$。总复杂度是 $\mathcal O(nd\log n)$。 代码没拿到，以后再来粘。