题目描述

有一棵 n 个节点的树，节点编号从 1 到 n ，树上的每条边都有流量限制。令某一个节点为根节点，向这个节点灌水，最终从叶子节点流出的水量之和为这个节点的最大流量。请求出每个节点的最大流量。

输入格式

第一行一个整数 n 表示节点数。

接下来 n−1 行，每行三个整数 x,y,z 表示 x 号节点和 y 号节点之间有一条流量限制为 z 的边。

数据保证读入的是一棵树。

输出格式

输出共 n 行，第 i 行一个整数表示 i 号节点的最大流量。

#include <bits/stdc++.h>
#define N 100010
#define WC 200010 //I'm angry
using namespace std;
typedef long long LL;
struct Node{
	Node *t;
	int m , v;
}*first[N] , a[WC];
int n , l;
LL f[N] , v[N];
bool b[N];
inline void join(int x , int y , int z){
	a[++l].m = y;
	a[l].v = z;
	a[l].t = first[x];
	first[x] = &a[l];
}
inline void up(int x){
	b[x] = true;
	bool ok = true;
	for(Node *i = first[x] ; i ; i = i->t)
		if(!b[i->m]){
			up(i->m);
			f[x] += min(1LL * i->v , f[i->m]);
			ok = false;
		}
	if(ok)
		f[x] = 1 << 30;
}
inline void down(int x){
	b[x] = true;
	for(Node *i = first[x] ; i ; i = i->t)
		if(!b[i->m]){
			v[i->m] = min(v[x] + f[x] - min(1LL * i->v , f[i->m]) , 1LL * i->v);
			down(i->m);
		}
}
int main(){
	scanf("%d" , &n);
	for(int i = 1 ; i < n ; ++i){
		int x , y , z;
		scanf("%d%d%d" , &x , &y , &z);
		join(x , y , z);
		join(y , x , z);
	}
	memset(b , false , sizeof(b));
	up(1);
	memset(b , false , sizeof(b));
	down(1);
	for(int i = 1 ; i <= n ; ++i)
		if(f[i] != 1 << 30)
			printf("%lld\n" , f[i] + v[i]);
		else
			printf("%lld\n" , v[i]);
	return 0;
}

在Input为

100000
1 2 174465933
2 3 933740970
3 4 721457355
4 5 634056295
5 6 563255423
6 7 318940157
7 8 10099...

输出为

8793
8793
8793
8793
8793
8793
8793
8793
8793
8793
8793
8793
8793
8793
8793
8793
8793
8793
8793
8793
...

万分感谢