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

称点 $i$ 子树中所有点点权的 $\operatorname{mex}$ 为 $d_i$。称 $u$ 的儿子构成集合 $son_u$，$u$ 的祖先构成集合 $anc_u$。不失一般性的称其中某个儿子 $v \in son_u$。

首先有一些基础的结论 $d_u \ge d_v,a_u > a_v$。

思考可以发现，我们可以将所有点 $u$ 分为两类：一类 $d_u=\max d_v$，另一类 $d_u > \max d_v$。对于第一类我们会把 $a_u$ 变的很大，用于提高 $u$ 的祖先的 $d$，即孝敬父亲。称第一类为白点，第二类为黑点。

最终形式会是：所有点 $d_u = \max d_v$（可以发现取到最大的 $v$ 一定是黑点）。然后对于每个白点，找到它祖先中第一个黑点的位置，并将它的 $d$ 增加一。

于是得到暴力 DP：$f_{u, i, j}$ 考虑 $u$ 的子树且 $d_u=i$ 且总共有 $j$ 个白点还没贡献的答案。$j=0$ 表示 $u$ 是黑点否则是白点。转移的话再开一个数组 $g_{i,j}$ 表示目前儿子中最大的 $d$ 为 $i$，以及有 $j$ 个白点。

最后：

考虑复杂度。$(u,j,j')$ 的总枚举量是树上背包，即 $\mathcal O(n^2)$。$(i,i')$ 还会有 $\mathcal O(n^2)$，可以前缀和优化到 $\mathcal O(n)$。总复杂度 $\mathcal O(n^3)$。不知道为啥没写前缀和就过了 48 分。

继续刻画。初始 $d_u = \max d_v$，这与最外层的 $\max$ 方向一致，于是可以放宽到任意钦定一个黑点 $v$ 为 $u$ 的重儿子，并继承它的 $d_v$。可以证明一个点一定存在至少一个黑儿子。这样会形成一个剖分的结构。而对于每个白点，找到它祖先中第一个黑点 $u$，那么它的贡献会让 $u$ 到它所在链顶的 $d$ 都加一，即它的贡献是 $u$ 所在重链的深度。称 $c_u$ 为 $u$ 所在重链的深度，即深度比它小的、和它在同一重链上的点的数量加一。这样我们就将贡献计算全放在了白点上。暴力做法可以 $\mathcal O(2^n)$ 枚举黑白点的掩码。

这样一条重链上只有链顶可能是白点，其余都是黑点。

换一种 DP。$f_{u,i}$ 表示考虑 $u$ 的子树的白点的贡献且 $c_u=i$ 的答案。转移枚举它的重儿子 $v$，则：