Aimee

很显然的做法就是枚举每个点为源点然后树形dp
$$
ds[x]=sum{yin son(x)} left{
begin{aligned}
min((D_s[y],c(x,y)))quad degeree_y>1 \
c(x,y) quadquadquadquadquadquadquad degree_y=1
end{aligned}
right.
$$
对于叶子节点要特判，不然的话经过叶子节点的流量就将会是0

这样整个方程意义何在

但是呢，这样的复杂度是$ o(n^2)$的,事实上对于根节点，我们可以从它开始一次把跟换成儿子

这样的话新根节点的流量由两部分组成，它子树的，和他父节点去掉他之后的部分

这样一个新源点的流量就会受他的d和父亲影响

这样的话往下推就可以了
$$
F_y=d_y+left{
begin{aligned}
min(f_x-min(d_y,c(x,y)),c(x,y))quad degree_x>1\
c(x,y)quad degree_x=1quad quadquadquadquadquadquadquadquadquadquad
end{aligned}
right.
$$
当根节点x是度数是1的时候需要特判

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t;
int n;
struct e{
    int to;
    int ne;
    int v;
}ed[500005];
int d[400005];
int znx[400005];
int x,y,z;
int head[400005];
int vis[400005];
int p;
void add(int f,int to,int ne){
    p++;
    ed[p].ne=head[f];
    ed[p].to=to;
    ed[p].v=ne;
    head[f]=p;
}

void dfs(int x,int f){
    for(int i=head[x];i;i=ed[i].ne){
        if(ed[i].to==f) continue;
        dfs(ed[i].to,x);
        if(vis[ed[i].to]!=1)
        d[x]+=min(d[ed[i].to],ed[i].v);
        else
        d[x]+=ed[i].v;
    }
}
void chan(int x,int f){
    for(int i=head[x];i;i=ed[i].ne){
        if(ed[i].to==f) continue;
        if(vis[x]==1){
            znx[ed[i].to]=d[ed[i].to]+ed[i].v;
        }else{
            znx[ed[i].to]=d[ed[i].to]+min(znx[x]-min(ed[i].v,d[ed[i].to]),ed[i].v);
        }
        chan(ed[i].to,x);
    } 
}
int main(){
    scanf("%d",&t);
    while(t--){
        memset(vis,0,sizeof(vis));
        p=0;
        memset(head,0,sizeof(head));
        memset(znx,0,sizeof(znx)); 
        memset(d,0,sizeof(d)); 
        scanf("%d",&n);
        for(int i=1;i<n;++i){
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z); 
            vis[x]++;
            vis[y]++;
        }
        dfs(1,0);
        znx[1]=d[1];
        chan(1,0);
        int Aimee=0;
        for(int i=1;i<=n;++i){
            Aimee=max(Aimee,znx[i]);
        }
        cout<<Aimee<<endl;
    }
    return 0;
}