Accumulation Degree

题意:选取任意一个节点为根节点,求最大流通流量
题解:参考第二题所给的遍历方法和换根方法,进行换根即可,只不过换根是式子变为
, 表示第一次搜索的在v节点的值, 表示第v个节点的答案.
第二题参考链接:https://blog.nowcoder.net/n/036d85b25e8c4d8aab55351f6d7134ca
code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int t,n,hd[N],tot,vis[N],d[N],f[N],deg[N],ans;
struct Edge{
    int v,nx,w;
}e[N<<1];
inline void add(int u,int v,int w)
{
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nx=hd[u];
    hd[u]=tot++;
}
void dp(int u)
{
    vis[u]=1;
    d[u]=0;
    for(int i=hd[u];~i;i=e[i].nx)
    {
        int v=e[i].v;
        if(vis[v])continue;
        dp(v);
        if(deg[v]==1)d[u]+=e[i].w;
        else d[u]+=min(d[v],e[i].w);
    }
}
void dfs(int u)
{
    vis[u]=1;
    for(int i=hd[u];~i;i=e[i].nx)
    {
        int v=e[i].v;
        if(vis[v])continue;
        f[v]=d[v]+min(f[u]-min(d[v],e[i].w),e[i].w);
        dfs(v);
    }
}
int main()
{

    scanf("%d",&t);
    while(t--)
    {
        memset(hd,-1,sizeof(hd));
        memset(vis,0,sizeof(vis));
        memset(f,0,sizeof(f));
        memset(d,0,sizeof(d));
        memset(deg,0,sizeof(deg));
        tot=0;ans=0;
        scanf("%d",&n);
        int u,v,w;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w),add(v,u,w);deg[u]++,deg[v]++;
        }
        dp(1);
        memset(vis,0,sizeof(vis));
        f[1]=d[1];
        dfs(1);
        for(int i=1;i<=n;i++)
            ans=max(ans,f[i]);
        printf("%d\n",ans);
    }
    return 0;
}