在列奧納多·達·芬奇時期，有一個流行的童年游戲，叫做“連珠線”。不出所料，玩這個游戲只需要珠子和線，珠子從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。
輸出一個整數，為游戲的最大得分。
數據范圍滿足1≤n≤200000。
樹形DP思路好題
假設初始節點為根，則藍線鏈接的點一定是父親-兒子-孫子關系。
先DP一次，然後再DFS，同時O(1)換根轉移。
DP信息在O(1)時間內轉移，從而枚舉到每一種情況的思路很好。
#include#include #include #include #include #include #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,j,n) for(int i=j;i>=n;i--) #define ll long long #define ull unsigned long long #define maxn 200005 #define inf 2000000005 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans,cnt,head[maxn],f[maxn]; struct edge_type{int next,to,v;}e[maxn*2]; struct data{int k,v;}d[maxn][2]; inline void add_edge(int x,int y,int v) { e[++cnt]=(edge_type){head[x],y,v};head[x]=cnt; e[++cnt]=(edge_type){head[y],x,v};head[y]=cnt; } inline void update(int x,int num,int v) { if (v>=d[x][0].v) d[x][1]=d[x][0],d[x][0]=(data){num,v}; else if (v>d[x][1].v) d[x][1]=(data){num,v}; } inline void dp(int x,int fa) { d[x][0].v=d[x][1].v=-inf; f[x]=0; for(int i=head[x];i;i=e[i].next) { int y=e[i].to; if (y==fa) continue; dp(y,x); int tmp=max(f[y],f[y]+d[y][0].v+e[i].v); f[x]+=tmp; update(x,y,f[y]+e[i].v-tmp); } } inline void dfs(int x,int fa) { ans=max(ans,f[x]); for(int i=head[x];i;i=e[i].next) { int y=e[i].to; if (y==fa) continue; int ff=f[y];data dd0=d[y][0],dd1=d[y][1]; int tmp=max(f[y],f[y]+d[y][0].v+e[i].v); int newfx=f[x]-tmp; int newk=d[x][0].k==y?1:0; int newtmp=max(newfx,f[x]+d[x][newk].v-tmp+e[i].v); f[y]+=newtmp; update(y,x,newfx+e[i].v-newtmp); dfs(y,x); f[y]=ff;d[y][0]=dd0;d[y][1]=dd1; } } int main() { n=read(); F(i,1,n-1) { int x=read(),y=read(),v=read(); add_edge(x,y,v); } ans=-inf; dp(1,0); dfs(1,0); printf("%d\n",ans); return 0; }
