Tutorial

If the root of a tree is fixed. Obvious, we can use tree dp to solve it. But the root are not fixed. Could we enumeration the roots, and do tree dp for every root? Obvious, the time complexity is . it will get TLE.
What should we do?
Let's first assume that the root of the tree is 1. Then we do tree dp. The answers saved in array .
We assume is mean the max accumulation degree when is root. Obvious, .
If we has been calculated , how to calculate its child node ?
The flow of subtree from is . The flow from to is
(dis(x,y) is mean the capacity between x and y)
So mean the flow from node to other(except node )
In summary, If the degrees of the node is one, , else,
Please see the follow code for detail.

code

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=2e5+5;
int head[N],ver[2*N],edge[2*N],Next[2*N];
int tot;
int v[N],deg[N];
ll d[N],f[N];
int n;

void add(int x,int y,int z)
{
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}

void init()
{
    tot=0;
    memset(head,0,sizeof(head));
    memset(v,0,sizeof(v));
    memset(deg,0,sizeof(deg));
}

void dp(int x)
{
    v[x]=1;
    d[x]=0;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(v[y])
            continue;
        dp(y);
        if(deg[y]==1)
            d[x]+=edge[i];
        else
            d[x]+=min(d[y],(ll)edge[i]);
    }
}

void dfs(int x)
{
    v[x]=1;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(v[y])
            continue;
        if(deg[x]==1)
            f[y]=d[y]+edge[i];
        else
            f[y]=d[y]+min(f[x]-min(d[y],(ll)edge[i]),(ll)edge[i]);
        dfs(y);
    }
}

void solve()
{
    init();
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
        deg[u]++;
        deg[v]++;
    }
    dp(1);
    f[1]=d[1];
    memset(v,0,sizeof(v));
    dfs(1);
    ll ans=*max_element(f+1,f+n+1);
    printf("%lld\n",ans);
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
        solve();
     return 0;
}