poj3585 Accumulation Degree(树形dp,换根)

/*
这就是一个树形dp（也就是依据树的边进行dp）
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
#define mem__(a) memset(a,-1,sizeof(a))
typedef long long ll;
const int maxn=200010;
const int INF=0x3f3f3f3f;
const double blo=(1.0+sqrt(5.0))/2.0;
const double eps=1e-8;
/*
child[x]表示以1为根节点情况下，以x为根的子树上能到达x节点上的最大流
然后你知道dp[x]和child[to]之后就可以求出来dp[to]
因为dp[x]减去从to这个子树上来的流量就是其他节点到x的流量，那么就可以知道其他节点到to节点的流量
 dp[to]=child[to]+min(dp[x]-min(e[i].dis,child[to]),e[i].dis);
 
*/
int n,head[maxn],child[maxn],du[maxn],dp[maxn],num;
struct Edge{
    int next,to,dis;
}e[2*maxn];
void add_edge(int from,int to,int dis){
    e[++num].next=head[from];
    e[num].to=to;
    e[num].dis=dis;
    head[from]=num;
}
int dfs_child(int x,int fa)
{
    int sum=0;
    for(int i=head[x];i!=-1;i=e[i].next)
    {
        int to=e[i].to;
        if(to==fa) continue;
        sum+=min(dfs_child(to,x),e[i].dis);
    }
    child[x]=sum;
    if(du[x]==1) return e[head[x]].dis;
    else return child[x];
}
void dfs(int x,int fa)
{
    for(int i=head[x];i!=-1;i=e[i].next)
    {
        int to=e[i].to;
        if(to==fa) continue;
        /*
        要加这个特判，因为如果我们的1点是一个叶节点（就是我们挑选了一个叶节点为根开始遍历），那么这个叶节点的子节点 
        的dp值就需要是加上child[to]，然后再加上父节点的边权，你画个图理解一下
        如果不加这个判断会卡下面这个数据，你按照这个数据画个图
        1
        3
        1 2 1
        2 3 1 
        */ 
        if(du[x]==1) dp[to]=child[to]+e[i].dis;
        else
        dp[to]=child[to]+min(dp[x]-min(e[i].dis,child[to]),e[i].dis);
        dfs(to,x);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        num=0;
        mem(child);
        mem(dp);
        mem(du);
        mem__(head);
        for(int i=1;i<n;++i)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            du[x]++;
            du[y]++;
            add_edge(x,y,z);
            add_edge(y,x,z);
        }
        dp[1]=dfs_child(1,-1);
        dfs(1,-1);
        int maxx=0;
        for(int i=1;i<=n;++i)
            maxx=max(maxx,dp[i]);
        printf("%d\n",maxx);
    }
    return 0;
}