标签：
【BZOJ3677】[Apio2014]连珠线 Description
在列奥纳多·达·芬奇时期，有一个风行的童年游戏，叫做“连珠线”。不出所料，玩这个游戏只需要珠子和线，珠子从1到礼编号，线分为红色和蓝色。游戏开始时，只有1个珠子，而接下来新的珠子只能通过线由以下两种方法被插手：
1．Append(w，杪)：-个新的珠子w和一个已有的珠子杪连接，连接使用红线。
2．Insert(w，u，v)：-个新的珠子w插手到一对通过红线连接的珠子（u，杪）之间，并将红线改成蓝线。也就是将本来u连到1的红线变为u连到w的蓝线与W连到V的蓝线。
无论红线还是蓝线，每条线都有一个长度。而在游戏的最后，将得到游戏的最后得分：所有蓝线的长度总和。
此刻有一个这个游戏的最终布局：你将获取到所有珠子之间的连接情况和所有连线的长度，但是你并不知道每条线的颜色是什么。
你此刻需要找到这个布局下的最大得分，也就是说：你需要给每条线一个颜色f红色或蓝色），使得这种连线的配色方案是可以通过上述提到的两种连线方法操纵得到的，并且游戏得分最大。在本题中你只需要输出最大的得分即可。
第一行是一个正整数n，暗示珠子的个数，珠子编号为1刭n。
接下来n-l行，每行三个正整数ai，bi(l≤ai10000)，暗示有一条长度为ci的线连接了珠子ai和珠子bi。
输出一个整数，为游戏的最大得分。
5
1 2 10
1 3 40
1 4 15
1 5 20
60
数据范畴满足1≤n≤200000。
题解：一开始想了个不换根的DP，，功效错了。。。
先选择一个点当根，那么所有的蓝线必然是 父-子-孙 这样的。于是我们令g[x]暗示当前点不是‘子‘的最大得分，f[x]暗示当前点是‘子‘的最大得分，树形DP即可。
但是我们如何换根呢？我们需要维护f的最大值和次大值，然后就能搞了。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn=200010; int n,cnt,ans; int to[maxn<<1],next[maxn<<1],val[maxn<<1],head[maxn],f1[maxn],g[maxn],f2[maxn]; inline void add(int a,int b,int c) { to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++; } inline int rd() { int ret=0,f=1; char gc=getchar(); while(gc<‘0‘||gc>‘9‘) {if(gc==‘-‘) f=-f; gc=getchar();} while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+(gc^‘0‘),gc=getchar(); return ret*f; } void dfs1(int x,int fa) { f1[x]=f2[x]=-1<<30; for(int y,i=head[x];i!=-1;i=next[i]) if(to[i]!=fa) { y=to[i],dfs1(y,x); int fy=g[y]+val[i]-max(g[y],g[y]+f1[y]+val[i]); if(fy>f1[x]) f2[x]=f1[x],f1[x]=fy; else if(fy>f2[x]) f2[x]=fy; g[x]+=max(g[y],g[y]+f1[y]+val[i]); } } void dfs2(int x,int fa) { ans=max(ans,g[x]); for(int y,i=head[x];i!=-1;i=next[i]) if(to[i]!=fa) { y=to[i]; int gx=g[x]-max(g[y],g[y]+f1[y]+val[i]),fx; if(f1[x]==g[y]+val[i]-max(g[y],g[y]+f1[y]+val[i])) fx=f2[x]; else fx=f1[x]; g[y]+=max(gx,gx+fx+val[i]); fx=gx+val[i]-max(gx,gx+fx+val[i]); if(fx>f1[y]) f2[y]=f1[y],f1[y]=fx; else if(fx>f2[y]) f2[y]=fx; dfs2(y,x); } } int main() { n=rd(); int i,a,b,c; memset(head,-1,sizeof(head)); for(i=1;i<n;i++) a=rd(),b=rd(),c=rd(),add(a,b,c),add(b,a,c); dfs1(1,0),dfs2(1,0); printf("%d",ans); return 0; }
【BZOJ3677】[Apio2014]连珠线 换根DP