题目描述

blablabla

样例

blablabla

算法

Y总讲的很好了,假如喜欢看vector代码,以及一些小小的改变的话就…看看这个题解吧

(换根dp) $O(n)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int inf=0x3f3f3f3f;
struct vv{
  int to,z;//点和容量.  
};

vector<vv>v[N];

int f[N],d[N],deg[N];//f数组表示这个做根能跑出来的max容量,d数组表示1为根这个点往下的子树最大分配流量,deg主要是用来判断叶子节点.

int dfs1(int u,int fa)//拿1作为根节点跑d数组.
{
    if(deg[u]==1)
    {
        d[u]=inf;
        return d[u];
    }
    d[u]=0;
    for(int i=0;i<v[u].size();i++)
    {
        int son=v[u][i].to;
        if(fa==son) continue;
        int w=v[u][i].z;
        d[u]+=min(w,dfs1(son,u));
    }
    return d[u];
}

void dfs2(int u,int fa)//根据d数组跑f数组.
{
    for(int i=0;i<v[u].size();i++)
    {
        int son=v[u][i].to;
        if(fa==son) continue;
        int w=v[u][i].z;
        if(deg[son]==1) f[son]=d[u]-w;
        else
        {
            f[son]=d[son]+min(w,f[u]-min(w,d[son]));
            dfs2(son,u);
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) v[i].clear();
        memset(deg,0,sizeof deg);
        memset(d,0,sizeof d);
        memset(f,0,sizeof f);
        for(int i=1;i<n;i++)
        {
            int x,y,e;
            scanf("%d%d%d",&x,&y,&e);
            v[x].push_back({y,e});
            v[y].push_back({x,e});
            deg[x]++;deg[y]++;
        }
        //建图.
        for(int i=1;i<=n;i++)
        {
            if(deg[i]!=1)//找一个度数不为1的
            {
                dfs1(i,-1);
                f[i]=d[i];
                dfs2(i,-1);
                break;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++) ans=max(ans,f[i]);
        if(ans==0)//不存在度数为1的.
        {
            ans=v[1][0].z;
        }
        printf("%d\n",ans);
    }
    return 0;
}