[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$，有两种情况：

$1.$ 若 $l\leq e_{rt}$，则实际上对于这条链，所有的 $e_i$ 取到 $e_{rt}$，取 $\text{max}$ 没有产生贡献，$\text{dp}$ 这样的一个结构即可 $O(nm)$。

$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)$，可以通过本题。