题目：http://poj.org/problem?id=3585
很容易想出暴力。那么就先扫一遍。
然后得到了指定一个根后每个点的子树值。
怎么转化利用一下呢？要是能找出当前点的父亲的 “ 不含当前点的其他子树值 ” 就好了。
发现只需要把父亲的值减去 min ( 当前子树的值，该点与父亲间的边的值 ) 就行了！（因为当初这样加过）
需要注意一下的是叶节点。赋成INF或边的值都行。
特别需要注意的是第一次选的根节点在其余时候是叶节点的情况！！！！！
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int T,n,xnt,head[],rd[],x,y,z,yt;
const int INF=;
long long d[],ans;
struct Node{
int next,to;
long long w;
}edge[];
void add(int x,int y,int z)
{
edge[++xnt].next=head[x];
edge[xnt].to=y;
edge[xnt].w=z;
head[x]=xnt;
rd[x]++;
}
void dfs1(int k,int fa)
{
if(rd[k]==&&k!=yt)
{
d[k]=INF;
return;
}
for(int i=head[k];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa)continue;
dfs1(v,k);
d[k]+=min(d[v],edge[i].w);
// printf("1 k=%d d=%lld\n",k,d[k]);
}
}
void dfs2(int k,int fa,int u)
{
long long r=d[fa]-min(d[k],edge[u].w);
if(rd[fa]==)r=edge[u].w;///////////////当根节点也是叶节点时！很特殊
if(rd[k]==)
{
d[k]=min(r,edge[u].w);
return;
}
d[k]+=min(r,edge[u].w);
// printf("2 k=%d d=%lld\n",k,d[k]);
for(int i=head[k];i;i=edge[i].next)
{
if(edge[i].to==fa)continue;
dfs2(edge[i].to,k,i);
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(head,,sizeof head);
memset(d,,sizeof d);
memset(rd,,sizeof rd);
xnt=;ans=-;///////
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
yt=;
dfs1(,);
for(int i=head[];i;i=edge[i].next)
dfs2(edge[i].to,,i);
for(int i=;i<=n;i++)ans=max(ans,d[i]);
printf("%lld\n",ans);
}
return ;
}