CF2217H 题解

前言

懒得喷。。。。。。

更可爱的阅读体验

思路

考虑树形 dp。在 dp 过程中枚举每个点的状态：没有进行交换，跟父亲交换或是跟某个儿子交换。将其记在状态里，用 $f_{u,0}$ 代表不交换，$f_{u,1}$ 代表跟父亲交换，$f_{u,i+2}$ 代表跟第 $i$ 个儿子交换（下标从 $0$ 开始）。有如下转移：

$\begin{cases} f_{u,0}=\sum\limits_{v\in son(u)}\max(f_{v,0}+[a_u=a_{v}]w_u,\max\limits_{x\geq 2}\{f_{v,x}+[a_u=a_{son(v)_x}]w_u\})\\ f_{u,1}=\sum\limits_{v\in son(u)}\max(f_{v,0}+[a_{fa_u}=a_{v}]w_{fa_u},\max\limits_{x\geq 2}\{f_{v,x}+[a_{fa_u}=a_{son(v)_x}]w_{fa_u}\})\\ f_{u,i(i\geq 2)} =f_{son(u)_i,1}+\sum\limits_{v\in son(u),v≠son(u)_i}\max(f_{v,0}+[a_{son(u)_i}=a_{v}]w_{son(u)_i},\max\limits_{x\geq 2}\{f_{v,x}+[a_{son(u)_i}=a_{son(v)_x}]w_{son(u)_i}\}) \end{cases}$

其中为了方便，记 $son(u)$ 代表点 $u$ 所有儿子构成的集合，$son(u)_i$ 代表 $son(u)$ 集合中的第 $i\color{red}-2$ 个元素，即 $u$ 的第 $i\color{red}-2$ 个儿子。同时用 $w_u$ 代表原数组的 $w_{a_u}$。

前两种转移直接暴力枚举 $u$ 的儿子及其儿子的儿子即可。每个点最多被其父亲和父亲的父亲枚举两次，复杂度依旧是 $\mathcal{O}(n)$。

由于每种 $a$ 只在树上出现两次，因此对于第三种转移，每次只可能有一个点的一个 dp 值发生变化。对于 $u$ 预处理 $sum=\sum\limits_{v\in son(u)} \max\limits_{x≠1}\{f_{v,x}\}$，枚举到儿子 $v$ 时先从 $sum$ 中减去 $v$ 的贡献并加上 $f_{v,1}$，再讨论与 $v$ 配对的点是 $u$ 的儿子还是 $u$ 的另一个儿子的儿子即可。