P3647 [APIO2014]连珠线 题解
题面
首先可以注意到一点：如果这棵树确定了根节点，那么所有的蓝边都只能是爷爷-父亲-儿子这样的边，不可能有儿子-父亲-另一个儿子这样的（建不出来）。
基于上述结论的一个 \(O(n^2)\) dp就是：枚举根节点，设 \(f_{u,0/1}\) 表示 \(u\) 节点子树中，\(u\) 是否作为某一条蓝边链中点的最大蓝边长度。转移方程说的是：
\[f_{u,0}=\sum_{v\in son_u}\max(f_{v,0},f_{v,1}+w(u,v)) \]\[f_{u,1}=f_{u,0}+\max_{v\in son_u}\{f_{v,0}+w(u,v)-\max(f_{v,0},f_{v,1}+w(u,v))\} \]现在考虑使用换根dp来优化。首先设 \(dp_{u,0/1,v}\) 表示 \(u\) 点不考虑 \(v\) 这个儿子的dp值，由于树上所有点的儿子总数是 \(O(n)\) 的，所以这个状态也是 \(O(n)\) 的。注意在计算 \(f_{u,1}\) 的时候，是首先记录了每个儿子信息的 \(\max\)。由于需要计算删掉一个儿子的dp值，有可能会删掉取到 \(\max\) 的那个儿子，所以在这里需要额外记录一个次大值。
考虑换根dp的过程：走到 \(v\) 点的时候，\(g_{u,0/1}\) 应该表示的是 \(u\) 除 \(v\) 以外的儿子以及父亲合并起来的dp值，这样在计算以 \(v\) 为根的答案时，只需要将它的父亲 \(u\) 也作为一个儿子合并dp值即可。这个方程不难转移（和上边是差不多的），然后就做完了。
注意换根dp的边界有些时候可能会出错，比如这个题需要尤其注意 \(fa=0\) 时的情况。
点击查看代码
#include
#include
#include
#define pb push_back
#define mp std::make_pair
#define fi first
#define se second
typedef std::pair pii;
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=2e5+13,INF=0x3f3f3f3f;
int n,f[N][2],g[N][2],ans,a[N];
std::vector dp[N][2];
std::vector e[N];
inline void add_edge(int u,int v,int w){e[u].pb(mp(v,w));}
void dfs1(int u,int fa){
f[u][1]=-INF;
int mx1=-INF,mx2=-INF,son1=0;
for(int i=0,lim=e[u].size();imx1) mx2=mx1,mx1=tmp,son1=v;
else if(tmp>mx2) mx2=tmp;
}
if(!son1) return;
f[u][1]=f[u][0]+mx1;
for(int i=0,lim=e[u].size();i