本文主要是介绍【洛谷P3647】[APIO2014]连珠线，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

前言

对于换根的理解应该和其他题解不一样，求过。

题解

首先分析题目简化题意：给定一棵树，从里面选出若干个“三连点”的边，使边权和最大。其中“三连边”有如下图两种形态：\(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\) 子树的贡献，根据前面的转移可以

这篇关于【洛谷P3647】[APIO2014]连珠线的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！