有一个树形的水系，由 $N-1$ 条河道和 $N$ 个交叉点组成。我们可以把交叉点看作树中的节点，编号为 $1-N$，河道则看作树中的无向边。每条河道都有一个容量，连接 $x$ 与 $y$ 的河道的容量记为$c(x,y)$。河道中单位时间流过的水量不能超过河道的容量。

　　有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。除了源点之外，树中所有度数为 $1$ 的节点都是入海口，可以吸收无限多的水，我们称之为汇点。也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。

　　在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。整个水系的流量就定义为源点单位时间发出的水量。

　　在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。

#include<bits/stdc++.h>
using namespace std;
namespace acac
{
	struct edge
	{
		int to,ne;
		long long v;
	}e[400010];
	long long H[200010],f[200010],DP[200010],sz[200010];
	int cnt=1;
	void add(int a,int b,long long v)
	{
		e[++cnt].to=b;
		e[cnt].ne=H[a];
		H[a]=cnt;
		e[cnt].v=v;
	}
	void dfs(int u,int fa)
	{
		sz[u]=0;
		int w=0;
		for(int i=H[u];i;i=e[i].ne)	
		{
			int v=e[i].to;
			if(v==fa)continue;
			sz[u]++; 
			w=1;
			dfs(v,u);
			f[u]+=min(f[v],e[i].v);
		}
		
		if(!w)f[u]=0xfffffff;
	//	if(u==4)cout<<f[u]<<"\n";
	} 
	long long ans=-1;
	void dp(int u,int fa)
	{
		ans=max(DP[u],ans);
		for(int i=H[u];i;i=e[i].ne)
		{
			int v=e[i].to;
			if(v==fa)continue;
			if(sz[u]==1&&!fa)DP[v]=f[v]+e[i].v;
			//if(v==10)cout<<DP[v]<<endl;
			else DP[v]=f[v]+min(e[i].v,DP[u]-min(e[i].v,f[v]));
			dp(v,u);
		}
	}
	int main()
	{
		int t,n,m;
		scanf("%d",&t);
		//if(t>2)return 0;
		while(t)
		{
			scanf("%d",&n);
			cnt=1;
			memset(f,0,sizeof(f));
			memset(H,0,sizeof(H));
			for(int i=1;i<=n-1;i++)
			{
				int a,b;
				long long c;
				scanf("%d%d%lld",&a,&b,&c);
				add(a,b,c);
				add(b,a,c);
			}
			dfs(1,0);
			for(int i=1;i<=n;i++)
			{
				if(f[i]==0xfffffff)f[i]=0;
				//cout<<f[i]<<" ";
			}
			DP[1]=f[1];
			dp(1,0);
			cout<<ans<<"\n";
			t--;
		}
		return 0;
	}
}
int main()
{
	acac::main();
	return 0;
}

具体思路是两轮dp,f算子树内的最大值，然后dp转移，但是只拿了12pts qwq

样例如下（多测，N<=200000，ans在int范围）

输入格式：

输入第一行包含整数T，表示共有T组测试数据。
　　每组测试数据，第一行包含整数N。
　　接下来N-1行，每行包含三个整数x,y,z，表示x，y之间存在河道，且河道容量为z。
　　节点编号从1开始。

intput:
1
5
1 2 11
1 4 13
3 4 5
4 5 10
output: 26