题目描述：
（题面有坑，概括一下：）
给出一棵$n$个点的无根树，每条边有价值。对于一个根，你可以令父节点-当前节点-子节点这两条边变成蓝色边。选一个点作根的价值是蓝色边边权之和，求最大价值。
题解：
树上换根dp。
设状态$w[u][0/1]$表示选择一个根后，点$u$不是/是“当前节点”时，子树的最大价值。
（转移有点长，请忽略无效细节谨慎食用）
首先有$w[u][0]=sumlimits _{fa[v]=u} max(w[v][0],w[v][1]+val(u,v))$，
当点$u$是叶子结点时$w[u][1]=- infty$；
不是的话，设$k[v]$表示在$w[u][0]$状态下，将点$u$的父节点、点$u$和点$v$染成蓝色的最大价值，有：
$w[v][0]>w[v][1]+val(u,v)$，$v$和$u$之间没有蓝边，那么$k[v]=val(u,v)$；
$w[v][0]<=w[v][1]+val(u,v)$，$v$和$u$以及$v$的儿子有蓝边，那么需要把$v$的状态改成$w[v][0]$，即$k[v]=w[v][0]-w[v][1]$；
那么$w[u][1]=w[u][0]+ max_{fa[v]=u} k[v]$。
换根过程模拟子节点对父节点贡献的变化。
把当前根$u$的儿子$v$换上去的话，先考虑$u$的减少。
最开始我们有：
$w[u][0]=sumlimits _{fa[v]=u} max(w[v][0],w[v][1]+val(u,v))$
$w[u][1]=w[u][0] + max_{fa[v]=u} k[v]$
对于$w[u][0]$，直接减那个东西（你们一定知道我说的是什么）。
对于$w[u][1]$，先减掉那个东西（还是那个东西），之后考虑最大值。若当前$v$的贡献为最大值，那么将那一项换成次大值。
对于$w[v][0]$，直接加那个东西（是$u$的那个东西）。
对于$w[v][1]$，预先求出$tmp=w[v][1]-w[v][0]$，此时$tmp$是上面转移式中的$max$一项。
用$u$的新贡献去更新$max$值即可。
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 200050; const int inf = 0x3f3f3f3f; template<typename T> inline void read(T&x) { T f = 1,c = 0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x = f*c; } int n,hed[N],cnt; struct EG { int to,nxt,w; }e[N<<1]; void ae(int f,int t,int w) { e[++cnt].to = t; e[cnt].nxt = hed[f]; e[cnt].w = w; hed[f] = cnt; } int w[N][2],s1[N],ans; int t1; void dfs0(int u,int fa) { w[u][0] = 0,w[u][1] = -inf; for(register int j=hed[u],to;j;j=e[j].nxt) if((to=e[j].to)!=fa) dfs0(to,u); int k1 = -inf,tmp = 0; for(register int j=hed[u],to;j;j=e[j].nxt) if((to=e[j].to)!=fa) { tmp+=max(w[to][0],w[to][1]+e[j].w); if(w[to][0]>w[to][1]+e[j].w)k1=max(k1,e[j].w); else k1=max(k1,w[to][0]-w[to][1]); } w[u][0] = tmp; if(k1!=-inf)w[u][1]=tmp+k1; } void dfs1(int u,int fa) { ans = max(ans,w[u][0]); int w0 = w[u][0],w1 = w[u][1]; int k1 = -inf,k2 = -inf;int son = -1; for(register int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; int now = (w[to][0]>w[to][1]+e[j].w)?e[j].w:w[to][0]-w[to][1]; if(now>=k1)k2=k1,k1=now,son=to; else if(now>k2)k2=now; } for(register int j=hed[u],to;j;j=e[j].nxt) if((to=e[j].to)!=fa) { int W0 = w[to][0],W1 = w[to][1]; int tmp = max(w[to][0],w[to][1]+e[j].w); w[u][0]-=tmp,w[u][1]-=tmp; if(to==son)w[u][1]=(k2==-inf)?k2:w[u][1]+k2-k1; tmp = max(w[u][0],w[u][1]+e[j].w); int dlt = w[to][1]-w[to][0],now = (w[u][0]>w[u][1]+e[j].w)?e[j].w:w[u][0]-w[u][1]; w[to][0]+=tmp;dlt = max(dlt,now); w[to][1] = w[to][0]+dlt; dfs1(to,u); w[to][0] = W0,w[to][1] = W1; w[u][0] = w0,w[u][1] = w1; } } int main() { read(n); for(int u,v,k,i=1;i<n;i++) { read(u),read(v),read(k); ae(u,v,k),ae(v,u,k); } dfs0(1,0),dfs1(1,0); printf("%d ",ans); return 0; }