题意

神仙题

【题目描述】
 有一个树形的水系，由 N-1 条河道和 N 个交叉点组成。
 我们可以把交叉点看作树中的节点，编号为 1~N，河道则看作树中的无向边。
 每条河道都有一个容量，连接 x 与 y 的河道的容量记为 c(x,y)。
 河道中单位时间流过的水量不能超过河道的容量。
 有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。
 除了源点之外，树中所有度数为 1 的节点都是入海口，可以吸收无限多的水，我们称之为汇点。
 也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。
 在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。
 除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。
 整个水系的流量就定义为源点单位时间发出的水量。
 在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。  
  【输入格式】
 输入第一行包含整数T，表示共有T组测试数据。
 每组测试数据，第一行包含整数N。
 接下来N-1行，每行包含三个整数x,y,z，表示x，y之间存在河道，且河道容量为z。
 节点编号从1开始。  
  【输出格式】
 每组数据输出一个结果，每个结果占一行。
 数据保证结果不超过2^31−1。  
  【数据范围】
N≤2*10^5  
  【输入样例】
1
 5
 1 2 11
 1 4 13
 3 4 5
 4 5 10   
  【输出样例】
26 

思路

我的妈呀，如果以前没做仓鼠找sugar II估计我还真做不出这道题目。

看到这种找根且还带树形DP的题目，脑子里面要马上树立一个正确的价值观，就是我们先固定一个根。

很明显，我们只要固定了一个根的话，算出他的流量不是手到擒来？

我们设\(f[i]\)表示这棵子树以\(i\)为汇点的话，那么流量是多少，随便DP一下就可以算出\(f[1]\)，同时我们又发现，我们貌似是可以\(O(1)\)转移的！

把当树根为\(1\)的情况转移到树根为\(2\)的情况貌似只用\(O(1)\)，即减去\(2\)对\(1\)的贡献，然后把\(1\)对\(2\)的贡献加到\(2\)，然后我们就可以算出树根为\(2\)的值了，那么我们再DFS一遍不就可以\(O(n)\)解决了吗？

当然根节点如果只有一个儿子的话那么转移到儿子后他的\(f\)为\(inf\)。

#include<cstdio>
#include<cstring>
#define  N  210000
#define  M  410000
#define  inf  2147483647
using  namespace  std;
struct  node
{
    int  y,c,next;
}a[M];int  len,last[N];
inline  void  ins(int  x,int  y,int  c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
int  f[N]/*表示的是以1为根的话，那么这个点的水流是多少*/,dp[N]/*表示以他为根时的答案。*/;
int  siz[N],dep[N];
int  n;
inline  int  mymin(int  x,int  y){return  x<y?x:y;}
inline  int  mymax(int  x,int  y){return  x>y?x:y;}
void  dfs1(int  x,int  fa)
{
    siz[x]=1;
    for(int  k=last[x];k;k=a[k].next)
    {
        int  y=a[k].y;
        if(y!=fa)
        {
            dep[y]=dep[x]+1;
            dfs1(y,x);
            f[x]+=mymin(f[y],a[k].c);siz[x]+=siz[y];
        }
    }
    if(siz[x]==1)f[x]=inf;
}
void  dfs2(int  x,int  fa)//表示以x为根的答案。 
{
    dp[x]=f[x];//索性继承 
    for(int  k=last[x];k;k=a[k].next)
    {
        int  y=a[k].y;
        if(y!=fa)
        {
            int  now=f[x];
            if(siz[x]-siz[y]==1  &&  dep[x]==0/*在根节点*/)f[x]=inf;
            else  f[x]-=mymin(f[y],a[k].c);
            if(siz[y]==1)f[y]=mymin(f[x],a[k].c);//特判这个点是不是叶子节点 
            else  f[y]+=mymin(f[x],a[k].c);
            dfs2(y,x);
            if(siz[y]==1)f[y]=inf;
            else  f[y]-=mymin(f[x],a[k].c);
            f[x]=now;
        }
    }
}
int  main()
{
    int  T;scanf("%d",&T);
    while(T--)
    {
        len=0;memset(last,0,sizeof(last));
        memset(f,0,sizeof(f));
        memset(dp,0,sizeof(dp));//暴力初始化
        scanf("%d",&n);
        for(int  i=1;i<n;i++)
        {
            int  x,y,z;scanf("%d%d%d",&x,&y,&z);
            ins(x,y,z);ins(y,x,z);
        }
        dfs1(1,0);
        dfs2(1,0);
        int  ans=0;
        for(int  i=1;i<=n;i++)ans=mymax(dp[i],ans);
        printf("%d\n",ans);
    }
    return  0;
}