这是一道二次扫描与换根法的裸题，见《算法竞赛进阶指南》第三版p290
主要是作为参考代码.（本代码转载自http://www.cnblogs.com/lmjer/p/9418902.html，并进行了一定的修改）
题目地址：http://poj.org/problem?id=3585
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=500010;
int cnt,ans,head[maxn],d[maxn],f[maxn],deg[maxn];
bool vis[maxn];
struct Edge{
int from,to,w,nxt;
}e[maxn*2];
void addEdge(int u,int v,int w){
e[++cnt].from=u;
e[cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void dfs1(int x){
vis[x]=1;
for(int i=head[x];i;i=e[i].nxt){
if(vis[e[i].to])continue;
int v=e[i].to;
dfs1(v);
if(deg[v]==1)d[x]+=e[i].w;
else d[x]+=min(d[v],e[i].w);
}
}
void dfs2(int x){
vis[x]=1;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;
if(vis[v])continue;
if(deg[x]==1)f[v]=d[v]+e[i].w;
else f[v]=d[v]+min(e[i].w,f[x]-min(e[i].w,d[v]));
ans=max(ans,f[v]);
dfs2(v);
}
}
void clearAll(){
ans=0,cnt=0;
memset(head,0,sizeof(head));
memset(d,0,sizeof(d));
memset(f,0,sizeof(f));
memset(deg,0,sizeof(deg));
memset(vis,0,sizeof(vis));
}
int main(){
int t;
scanf("%d",&t);
while(t--){
clearAll();
int n;
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
deg[u]++;
deg[v]++;
}
int root=1;
dfs1(root);
memset(vis,0,sizeof(vis));
f[root]=d[root];
dfs2(root);
printf("%d
",ans);
}
return 0;
}