传送门
前言
对于换根的理解应该和其他题解不一样,求过。
题解
首先分析题目简化题意:给定一棵树,从里面选出若干个“三连点”的边,使边权和最大。其中“三连边”有如下图两种形态:\(3-1-2\) 和 \(3-5-6\)
(图源:tommymio)
一开始我想到一种 DP:\(dp(u,0/1/2)\) 表示 \(u\) 节点的子树内可以向下延伸的边数为 \(0/1/2\) 时的最大值,希望通过类似容斥解决形如 \(3-1-2\) 的情况,但实际不太可行(也可能只是我没做出来)。
换一种思路,\(dp(u,0/1)\) 表示 \(u\) 是/不是蓝线中点时,子树内答案的最大值。
- 如果 \(u\) 不是中点,那对于一个儿子 \(v\),\(v\) 可以是中点也可以不是中点,就有转移式:\(dp(u,0)=\max\{dp(v,1)+w,dp(v,0)\}\)
- 如果 \(u\) 是中点,其实是对于它的一个儿子,\(u\) 是中点,进行“\(u\) 是中点”的转移,即 \(dp(v,0)+w\);但是对于其他儿子 \(u\) 依旧不是中点,所以转移同上。综合一下就是 \(dp(u,1)=dp(u,0)+\max\{dp(v,0)+w-\max\{dp(v,1)+w,dp(v,0)\}\}\)。
换根!
但是这样做只考虑了竖着的“三连点”,可以发现通过不断换根的位置,可以使树里所有 \(3-1-2\) 形态的选法都变成竖着的。
不能枚举根,所以考虑换根。
记录 \(up(u,0/1)\) 表示 \(u\) 是/不是蓝线中点时,子树外答案的最大值。(换根 DP 都这么设,我这里的子树外是指刨去子树的其他部分)。
先看图:
考虑当前从点 \(u\) 向下走到儿子 \(v\),更新 \(up(v,0/1)\),显然是从红色部分和蓝色部分来更新。其中蓝色部分是和 \(up(u)\) 有关,红色部分是和 \(dp(u),dp(v)\) 有关。
- 对于红色部分,相当于从 \(dp(u)\) 里撤销 \(v\) 子树的贡献,根据前面的转移可以