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

· · 题解

首先我们会发现 mex 是由传递性的，一个结点的 mex 取决于子树里出现的最小缺失值。我们钦定子树里出现了 0,1,...,d-1 这些权值，那么该结点的 mex 至少是 d。而且这些值会同时出现在所有祖先的子树里，使祖先的 mex 也增加。

现在我们希望可以保证前缀，那么就必须沿着某一条链逐层扩展，并且这个链必须满足：深度为 d 的节点，贡献必须为 d，链上的所有祖先都会受益。

这样的链就是重链。

对于不在重链上的子树（我们称其为轻子树）我们希望我们给其附上的权值可以出现在父亲和祖先的子树上，从而给重链带来正贡献。

这样我们就可以得到一个 m \le 2 的做法了，答案即等于所有节点的子树大小乘上深度之和。

但是这样显然有问题，不妨设每个节点有一个自己的最大贡献，那么这个最大贡献至少是子树大小乘上深度（即直接吸收子树）。

考虑什么会对最大贡献产生影响，容易知道，我们只要知道节点 u 和其所在的链的深度即可。

所以设 dp_{u,d} 为结点 u 在一条链深为 d 的重链上时，整棵子树的最大价值。

令：

dp_{u,d}=d+\sum_{v\in son(u)} \max(size_v\cdot d, dp_{v,0})

其中 d 为 u 本身的贡献。

意思为要么直接吸收，要么独立。

或者可以延长重链：

dp_{u,d} = \max(dp_{u,d},\ \max_{v\in son(u)} (dp_{u,d} - \max(size_v\cdot d, dp_{v,0}) + dp_{v,d+1}))

意义为：只能选一个孩子延长，而且延长完要剪掉其贡献，改为延长链的贡献。

边界是叶子节点的值为深度。

但是，直接转移复杂度是 nm\cdot\deg(u) 的，显然无法通过，考虑优化。

令 g_{u,d} 为结点 u 自己就在一条链深为 d 的重链上时，整棵子树的最大价值。

显然转移也是分为不延和延长。

故 g_{u,d}=\max(g_{u,d}, s_{u,d})（不延长）或 \max(g_{u,d}, s_{u,d} - dp_{v,d} + g_{v,d+1})。

其中 s_{u,d}=d + \sum_{v \in son(u)} dp_{v,d}。

所以 dp 的转移被我们改写成：

dp_{u,d}=\max(dp_{u,d},\max_{v\in son(u)}(g_{v,d+1}+(d-1 + \sum_{x \in son(u)} dp_{x,d-1}) - dp_{v,d-1}))

乍一看是变糖了，实际上我们可以用一个分层树状数组去维护 (d-1 + \sum_{x \in son(u)} dp_{x,d-1}) - dp_{v,d-1})。

维护这样一个 BIT，在 u 的每个孩子 v 都执行一遍子树加 s_{u,d}-dp_{v,d}（d 是层数）

假设子树 u 的 dfs 序的区间起点是 d_u。

则 (d-1 + \sum_{x \in son(u)} dp_{x,d-1}) - dp_{v,d-1})=query(d_v)。

即等于 d 层 d_v 这个点处的值。

从下向上做一次即可，复杂度 nm \cdot \log n。