Accumulation Degree

题意：
给予你一棵n个节点的树，每一条边有一个容量，你选择一个节点当根，求从根节点到叶子节点的流量的最大值。

思路：
树状dp+换根：
flow[i]为以i为子树i到子树叶子节点的流量最大值。
ans[i]表示以i为根节点时的答案。
flow[u]= min(flow[v],cost(u,v))(v为u的子节点)。
换根：
ans[v]+=min(cost（u,v）,ans[u]-min(cost（u,v）,flow[v]));(为了节约空间，ans和flow可以共用一个数组)。

代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define inf 998244353

int n;
struct w
{
    int to, cost;
}w[200005], w1;

vector<struct w> g[200005];

int flow[300005];

int dfs(int v,int f)
{
    if(g[v].size()==1&&f!=-1)
    {
        flow[v]=g[v][0].cost;
        return flow[v];
    }
    int z=0;
    for(int i=0; i<g[v].size(); i++)
    {
        if(g[v][i].to==f)
        {
            continue;
        }
        z=z+min(dfs(g[v][i].to,v),g[v][i].cost);
    }
    flow[v]=z;
    return z;
}

void dfs1(int v,int f)
{
    if(g[v].size()==1&&f!=-1)
    {
        return ;
    }
    for(int i=0; i<g[v].size(); i++)
    {
        if(g[v][i].to==f)
        {
            continue;
        }
        flow[g[v][i].to]+=min(g[v][i].cost,flow[v]-min(g[v][i].cost,flow[g[v][i].to]));
        dfs1(g[v][i].to,v);
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        fill(flow,flow+300005,inf);
        scanf("%d",&n);
        for(int i=0; i<n-1; i++)
        {
            int s, e, cost;
            scanf("%d %d %d",&s,&e,&cost);
            w1.cost=cost;
            w1.to=e;
            g[s].push_back(w1);
            w1.to=s;
            g[e].push_back(w1);
        }
        dfs(1,-1);
        dfs1(1,-1);
        int ma=-1;
        for(int i=1; i<=n; i++)
        {
            ma=max(ma,flow[i]);
        }
        printf("%d\n",ma);
        for(int i=1;i<=n;i++)
        {
            g[i].clear();
        }
    }
    return 0;
}