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

· · 题解

::::info[记号说明]

$\text{son}_u$：$u$ 的子节点组成的集合。 $\text{path}_{u, v}$：树上 $u$ 到 $v$ 的简单路径上的点组成的集合。 :::: 以下内容参考了其它题解。 记每个点填的数为 $a_u$，答案为 $b_u$，另记 $x = \text{mex}_{v\in \text{subtree}_u} a_v$，称 $a_u=x$ 的点为黑点，否则为白点。显然，$a_u \ge x$。 白点的作用一定是为黑点产生贡献，可以理解成是将一个白点分配给一个唯一的黑点，让这个黑点的贡献 $+1$。 容易设计出一个状态：$f_{u, i, j}$ 表示 $u$ 子树内（不包括 $u$ 本身） $x = i$，有 $j$ 个白点的最大价值和。转移即枚举 $b_u$ 与 $\max_{v \in son_u} {b_v}$ 的差，表示将这么多个白点分给 $u$，再枚举一个取到 $\max b_v$ 的 $v$，可以做到 $\mathcal{O}(n^4)$ 或 $\mathcal{O}(n^3)$。 我们考虑这个取到最大值的儿子 $v$，我们令其为重儿子（和重链剖分没有关系），那么树就被剖分成了若干链，且每次 $b_u \leftarrow b_u + 1$，都会使 $u$ 到该链的链顶这些点 $b + 1$ 即分一个白点给 $u$ 的贡献为 $\text{dep}_u$。注意这里的 $\text{dep}_u$ 是指其到链顶的路径上的**点数**。所以一个白点的最大贡献就是其到根节点路径上节点个数最多的链。 考虑 $f_{u, i, j}$ 表示 $u$ 所在链的长度为 $i$，$\text{dep}_u=j$ 的答案（$\text{dep}_u$ 定义同上）。这个的转移是 $\mathcal{O}(nm^2)$ 的。 考虑优化，发现其实 $j = 1$ 和 $j = i$ 的情况就足够了：$f_{u, i}$ 表示 $u$ 是链顶，$u$ 到根节点路径上长度最长的链长为 $i$ 的答案，$g_{u, i}$ 表示 $u$ 是其所在链链底，到根节点路径上长度最长的链长为 $i$ 的答案。 注意这里的链长都是指节点个数。 初始时 $f_{u, i}, g_{u, i}$ 都为 $i \times sz_u$。 $g$ 的转移： $$g_{u, i} = \max_{v \in \text{son}_u} j + g_{v, i + 1} + \sum_{w \in \text{son}_u \land w \neq v} f_{w, i}$$ $f$ 的转移：考虑枚举一个与 $u$ 距离为 $i - 1$ 的后代 $v$ 代表链底，有转移： $$f_{u, i} \leftarrow i(i - 1) + g_{v, i} + \sum_{w \in \text{path}_{u, v} \land w \neq u}\sum_{x \in \text{son}_{fa_w \land x \neq w}} f_{x, i}$$ 后面这一坨代表其它链，$i(i - 1)$ 是 $b_u$。 枚举 $v$ 的复杂度是 $\mathcal{O}(nm)$ 的，因为每个点最多有 $m$ 个祖先。 使用树状数组即可做到 $\mathcal{O}(nm \log n)$。