Accumulation Degree题解

这道题我非常无语 各种爆空间，超时，初始化不可以memset 而且有强迫症的喜欢1e6空间的也会被卡死，注意这道题就是开1e5花里胡哨的开法，都给我卡死了 ，一下午就被一个初始化给搞来得40分；
废话不多说，题意就是让你在这个图中找一个源点，然后求最大流量，是不是就和网络流里面的最大流一样，求流量。
首先，这个题我们有很多个点，所以我们要知道一个东西，叫换根。首先我们以1为根，跑一次塔的最大值，然后在跑一次，换不同的根，更新。代码里面解释

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof b);
using namespace std;
const int maxx=2e5+100;//不要开大了，要爆空间
const int mod=1e9+7;
struct node
{
    int to,val;
    node(int x=0,int y=0):to(x),val(y){}
};
vector<node>ans[maxx];
int f[maxx]///每个点得最大值；
//f[v] 包括两部分：一部分是从 v 流向自己的子树，一部分是从 v 往父节点走。
int d[maxx];
int du[maxx]//度;
void init()
{
    for(int i=1;i<=2e5;i++)
       f[i]=0,d[i]=0,du[i]=0, ans[i].clear();
}
void add(int u,int v,int val)
{
    ans[u].push_back(node{v,val}),du[u]++;
    ans[v].push_back(node{u,val}),du[v]++;
}
void dp(int u,int fa)
{
    for(int i=0;i<ans[u].size();i++)
    {
        int v=ans[u][i].to;
       // cout<<v<<endl;
        int val=ans[u][i].val;
        if(v==fa) continue;
        dp(v,u);
        if(du[v]==1) d[u]+=val;//如果子节点得度为一那么就是叶子节点直接让它得父节点加上它的权值
        else
            d[u]+=min(val,d[v]);//每次比较自己的边和所有儿子的边权 取min
    }
}
void dfs(int u,int fa)
{
    for(int i=0;i<ans[u].size();i++)
    {
        int v=ans[u][i].to;
        int val=ans[u][i].val;
        if(v==fa) continue;
        if(du[u]==1) f[v]=d[v]+val;// 特判如果自己度是1
        else f[v]=d[v]+min(f[u]-min(val,d[v]),val);//更新每次的贡献
        dfs(v,u);
    }
}
int main()
{
    fio;
    int a;
    cin>>a;
    while(a--)
    {
        init();
        int n;
        cin>>n;
        for(int i=1;i<n;i++)
        {
            int u,v,val;
            cin>>u>>v>>val;
            add(u,v,val);
        }
        dp(1,0);
        f[1]=d[1];
        dfs(1,0);
        int an=0;
        for(int i=1;i<=n;i++)
            an=max(an,f[i]);//遍历所有得值 找最大值
        cout<<an<<endl;
    }



    return 0;
}