一道二次扫描换根法的树形DP,
具体来说就是先自底而下统计子树信息,再自顶而下更新全局信息。
对于这道题,有$d_i$是以$i$为根的子树的最大流量,$f_i$是以$i$为源点的最大流量,由于$d_i$已经被求出来了,那么$f_i$就很好求了。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=2e5+10;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int y,c,next;}a[N<<1];int len,last[N];
inline void ins(int x,int y,int c){a[++len]=(edge){y,c,last[x]};last[x]=len;}
int d[N];//把x当作源点流向子树的最大流量
int f[N];//把x当作源点流向整个水系的最大流量
int deg[N];
void treedp(int x,int fa)//自下而顶 
{
    d[x]=0;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y==fa)continue;
        if(deg[y]==1)d[x]+=a[k].c;
        else treedp(y,x),d[x]+=min(a[k].c,d[y]); 
    }
}
void dfs(int x,int fa)//自顶而下 
{
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y==fa)continue;
        f[y]=d[y];
        if(deg[x]==1)f[y]+=a[k].c;
        else f[y]+=min(f[x]-min(d[y],a[k].c),a[k].c);
        //x流向整个水系的量减去(以y为源点流向子树的量,与边权取min值,就为x流向y的量)x流向y的量,再与边权取min值,即限定流量上限之后,为y流向整个水系除子树外的流量。
        dfs(y,x); 
    }
}
int main()
{
    int T;qr(T);
    while(T--)
    {
        int n;qr(n);memset(deg,0,sizeof(deg));len=0;memset(last,0,sizeof(last));
        memset(d,0,sizeof(d));memset(f,0,sizeof(f));
        for(int i=1,x,y,c;i<n;i++)qr(x),qr(y),qr(c),ins(x,y,c),ins(y,x,c),++deg[x],++deg[y];
        treedp(1,0);f[1]=d[1];
        dfs(1,0);int ans=0;
        for(int i=1;i<=n;i++)ans=max(f[i],ans);
        qw(ans);puts("");
    }
    return 0;
}