P14637

· · 题解

Tree

设 u 点权 a_u，价值 b_u，你要最大化的即 \sum_u b_u。

考虑 a_u 的分配，设 x=\text{mex}_{v\in \text{sub}_u-\{u\}}a_v，按 a_u 分为取 x 和 >x 两种情况。两类点 b_u 都已经确定，而后者的存在是为了增加 u 某个祖先的 b_v，不妨放到对应祖先处确定具体值。

设 f_{u,i,j} 为子树 u 内已确定的 a_v 求 \text{mex} 为 i，j 个点未确定，此时最大价值，转移即枚举 b_u-\max_{v\in \text{son}_u}b_v。

不妨钦定某个 v 处取到 \max，这形成一个链剖，在这个结构上考虑 b_u 在 \max_vb_v 基础上每次 +1 的贡献，即对 u 到 \text{tp}_u 这条链上所有点 b 值 +1，其对总答案的贡献即链内深度（1-index），设之 d_u。

换言，初始 d_1=1，每个 u 恰选择一个重儿子 v 使 d_v=d_u+1，其余 d_v=1，最大化 \sum_u(\max_{v\in \text{anc}_u}d_v)。

设 f_{u,i} 表示: 钦定 u 为其所在重链的 tp，u 祖先链上的 d_{\max} 为 i，此时 u 子树的最大价值和。

为了处理更新 d_{\max} 的情况，再令 g_{u,i} 表示 u 为其所在重链中间一个点，祖先链 d_{\max} 在 u 处取到 i，子树价值。

每个深度开线段树做到 $O(nm\log n)$，长剖技巧做到 $O(nm)$，此处不再赘述。 另一个视角是想要更直观地刻画贡献给祖先的点的贡献，下将 $a_u=x$ 的点称作黑点，$a_u>x$ 称为白点。 发现黑点 $u$ 一定可以有黑点儿子，否则取子树黑点 $\text{mex}$ 最大的儿子 $v$，交换 $a_u,a_v$ 不劣，这样 $v$ 成为黑点。 将这个 $v$ 看作 $u$ 的重儿子，黑点内部形成链剖，此时白点 $u$ 所贡献即是其祖先中深度最小的黑点 $v$，否则将 $v$ 改成白点和 $u$ 贡献给同一个点不劣。 设 $f_{u,i}$ 为 $u$ 最深祖先黑点链内深度为 $i$ 时的子树 $u$ 的最大价值，这是为了处理首个黑点祖先在子树外的那些点，转移同样可以优化。 参考了 CommonAnts 的题解，感谢他耐心给我讲。