题目意思:给出一个无向图,n个顶点,n-1条边。每条边有权值w,表示流量。

流量:本来我实在没理解题目样例的解释,后来问了一位大佬的解,秒懂了.其实边权可以理解成水管的粗细,水能流多少。

比如1->4-3 首先1->4可以通过13的水,由于4->3水管只有5的大小,所以1-4-3只能流出5.
再比如1->4->5 之前1->4->3 已经流出了5 那么1->4->5 剩下还有8,粗细为10的可以全部通过,所以1->4->5流出是8.

题目要求的是,以某个点为根,计算根到所有叶子节点的流量和
最后再取最大值

好了题意应该理解了。。。。

分析:这是一道换根dp题,思路就是换根之后和换根之前的贡献差异,推出转移方程即可。

首先分成2种情况:
第一种换根节点为叶子节点（比较特殊）
如图所示:

图片说明 

第二种换根节点不是叶子节点（常规情况）

如图所示：
图片说明

这里注意的是，如果用一个数组来存结果，那么中间变动的值不能改变。详细看代码细节。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int N=200000+100;

int t;
int n;
int x,y,z;

int head[N],tot;
int isleaf[N];//判断是不是叶子节点 
int f[N];//每个节点总贡献 

struct Edge
{
    int e;
    int to;
    int w;//权值 
}edge[N<<1];

void add_edge(int u,int v,int val)
{
    tot++;
    edge[tot].e=v;
    edge[tot].to=head[u];
    edge[tot].w=val;
    ++isleaf[u];//每次加边的时候，由于我们正反2次加，所以叶子节点最后的isleaf值一定是2 
    ++isleaf[v];
    head[u]=tot;
}

void init()
{//初始化函数 
    memset(head,0,sizeof(head));
    tot=0;
    for(int i=0;i<N;i++)
    {
        edge[i].e=0;
        edge[i].to=0;
        edge[i].w=0;
    }
    memset(isleaf,0,sizeof(isleaf));
    memset(f,0,sizeof(f));
}

void dfs(int u,int fa)
{//第一次dfs,计算从1为根的所有点的流量 
    for(int i=head[u];i!=0;i=edge[i].to)
    {
        int v=edge[i].e;
        int w=edge[i].w;
        if(v==fa)continue;
        dfs(v,u);
        //如果是叶子节点，直接加上流量，不是叶子节点，和当前权值取最小值即可 
        if(isleaf[v]==2)f[u]+=w;
        else f[u]+=min(f[v],w);
    }
}

void dfs2(int u,int fa)
{
    for(int i=head[u];i!=0;i=edge[i].to)
    {
        int v=edge[i].e;
        int w=edge[i].w;
        if(v==fa)continue;
        //把根换做v
        if(isleaf[v]==2)f[v]+=w;//叶子节点的时候 
        else 
        {
            int k=f[u]-min(f[v],w);//用一个临时变量存一下，不能直接改变. 
        //    f[u]-=min(f[v],w);这样写是错的 
            f[v]+=min(w,k);
        }
        dfs2(v,u);
    }
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d",&n);
        for(int i=0;i<n-1;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            add_edge(x,y,z);
            add_edge(y,x,z);
        }
//        for(int i=1;i<=n;i++)
//        {
//            if(isleaf[i]==2)
//            {
//                printf("%d is leap\n",i);
//            }
//            else
//            {
//                printf("%d is not leap\n",i);
//            }
//        }
        dfs(1,0);
//        for(int i=1;i<=n;i++)
//        {
//            printf("f[%d]:%d\n",i,f[i]);
//        }
    //    printf("f[1]:%d\n",f[1]);

        dfs2(1,0);

//        for(int i=1;i<=n;i++)
//        {
//            printf("f[%d]:%d\n",i,f[i]);
//        }
        int maxx=-1e9;
        for(int i=1;i<=n;i++)
        {
            maxx=max(maxx,f[i]);
        }
        printf("%d\n",maxx);
    }
    return 0;
}