有一个树形的水系，由 N-1 条河道和 N 个交叉点组成。

我们可以把交叉点看作树中的节点，编号为 1~N，河道则看作树中的无向边。

每条河道都有一个容量，连接 x 与 y 的河道的容量记为 c(x,y)。

河道中单位时间流过的水量不能超过河道的容量。

有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。

除了源点之外，树中所有度数为 1 的节点都是入海口，可以吸收无限多的水，我们称之为汇点。

也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。

在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。

除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。

整个水系的流量就定义为源点单位时间发出的水量。

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

输入格式
输入第一行包含整数T，表示共有T组测试数据。

每组测试数据，第一行包含整数N。

接下来N-1行，每行包含三个整数x,y,z，表示x，y之间存在河道，且河道容量为z。

节点编号从1开始。

输出格式
每组数据输出一个结果，每个结果占一行。

数据保证结果不超过231−1。

数据范围
N≤2∗105

输入样例：
1
5
1 2 11
1 4 13
3 4 5
4 5 10

输出样例：
26

一眼看到题目，以为是SW求无向图最小割，但是数据太大，而且给的是一棵树。

于是我们可以想到，二次扫描之后换根即可。然后我们记录出来以1节点为根的最大值，然后换根即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f;
int T,n,deg[N],d[N],f[N],res;
int head[N],nex[N<<1],to[N<<1],w[N<<1],tot;
inline void add(int a,int b,int c){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void init(){
	tot=res=0;	memset(head,0,sizeof head); memset(deg,0,sizeof deg);
	memset(d,0,sizeof d); memset(f,0,sizeof f);
}
void dfs1(int x,int fa){
	if(deg[x]==1)	d[x]=inf;
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue; dfs1(to[i],x);
		d[x]+=min(w[i],d[to[i]]);
	}
}
void dfs2(int x,int fa){
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue;
		if(deg[to[i]]==1)	f[to[i]]=min(w[i],f[x]-w[i]);
		else	f[to[i]]=d[to[i]]+min(w[i],f[x]-min(d[to[i]],w[i]));
		dfs2(to[i],x);
	}
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n; init();
		for(int i=1,a,b,c;i<n;i++)	
			scanf("%d %d %d",&a,&b,&c),add(a,b,c),add(b,a,c),deg[a]++,deg[b]++;
		dfs1(1,1); f[1]=d[1]; dfs2(1,1);
		for(int i=1;i<=n;i++)	res=max(res,f[i]);
		cout<<res<<endl;
	}
	return 0;
}