[NOIP2025] 树的价值

· · 题解

首先可以考虑 \text{mex} 如何刻画，由于 \text{mex} 本身是最大化，与问题中 \text{mex} 的和的最大化方向相同，所以可以将条件弱化为每一个节点 i 钦定一个 d_i，使得子树内 [0,d_i-1] 均出现过，使得 \sum_{i=1}^{n}d_i 最大化。

如果只考虑对于一个序列 d 判定合法性，那么这可以被看作一个树上的匹配问题，每次 d_i 首先至少可以达到 \max_{x\in \text{son}(i)}d_x，如果要使得 d_i 取到更大，则每加大 1，需要在子树中选一个未被赋值的节点赋值成现在的 d_i，则 d_i 可以增大 1。直接 \text{dp} 匹配可以做到 O(n^3)。

进一步的，考虑弱化 d_i=\max_{x\in son(i)}d_x 再逐步增大的限制，这里的 \text{max} 与答案的 \text{max} 方向也是相同的，这相当于钦定一个 x_i\in \text{son}(i)，让 d_i 取到 d_x，然后可以不断通过匹配子树中未被赋值的点赋值来 +1。

这样对于一个确定的 x，其构成了一个剖分，对于一次 d_i 的 +1，其可以使得 x 到 x 所在的链的顶端的 d 加 1，故这个点对答案产生的贡献为其在链上的深度(即在链剖分中其所在的链中比其小的深度的个数加 1，下文中令 i 在链上的深度为 c_i)。那么对于每一个未匹配的点 x，使其在 \max_{x\in \text{son}(y)}c_y 最大一个产生贡献最优，故仅 \text{dp} 链剖分的 c 并记录每个点到根结点这条路径 c 的最大值不难做到 O(nm^2)。

实际上我们 \text{dp} 的问题变成了这样一个结构：根节点 c_{1}=1，且对于每一个节点 x，若其不是叶子，则恰好存在一个 y\in \text{son}(x) 使得 c_y=c_x+1，其余儿子的 c 均为 1。求 \sum_{i=1}^{n}\max_{i\in \text{son}(j)}c_j 的最大值。一个自然的优化想法是仅对于每个节点 i，仅\text{dp} e_i=\max_{i\in \text{son}(j)}c_j。

现在考虑问题变成了怎样的结构，不难发现实际上对于 e_i 的取 \text{max} 可以通过每一次对链的取 \text{max} 进行。每次将根所在的链对 c 取 \text{max}，删除这条链，则其余的子树可以看作若干个子问题，每个子树的根可以看作原问题的根。考虑 \text{dp} 这个结构，对于根所在的链对 c 的取 \text{max}，令链的长度为 l，目前的根为 rt，有两种情况：

$2.$ 若 $l>e_{rt}$，则将分为两部分，对于链上 $c_i\leq e_{rt}$ 的节点 $i$，$e_i=e_{rt}$；对于链上 $c_i>e_{rt}$ 的节点 $i$，$e_i=c_i$。考虑在 $c_p=e_{rt}$ 的点上统计贡献，子树内的结构(即 $c_i>e_{rt}$ 的节点)是简单的，可以简单 $\text{dp}$ 做到 $O(nm)$。而对于 $c_i<e_{rt}$ 的节点，相当于在断掉 $p$ 到祖先这条链后，除了 $p$ 子树外的其他子树中根的 $e$ 取到 $e_{rt}$ 的会对 $\text{dp}$ 的结果产生贡献。这是一个经典的问题(人造情感)，在每次 $\text{dp}$ 完一个点后，对于每一个以该节点的儿子为根的子树，让该节点儿子为根的其他子树的 $\text{dp}$ 对其进行子树加即可，这可以用树状数组快速维护，做到 $O(nm\log n)$。 故复杂度可以做到 $O(nm\log n)$，可以通过本题。