《算法竞赛进阶指南》 第六章 287. 积蓄程度

// 502 extra.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
287. 积蓄程度
https://www.acwing.com/problem/content/289/

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

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

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

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

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

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

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

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

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

整个水系的流量就定义为源点单位时间发出的水量。
0.
在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。

输入格式
输入第一行包含整数 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
*/



#include <iostream>
#include <algorithm>
#include <cstring>


using namespace std;

const int N = 200010;
int h[N], e[2 * N], ne[2 * N], w[2 * N], idx;
int  dp[N], v[N];
int n;

void add(int a, int b,int c) {
	e[idx] = b, w[idx]=c,ne[idx] = h[a], h[a] = idx++;
}

void up(int u, int fa) {
	bool isleaf = true;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i]; int c = w[i];
		if (j == fa) continue;
		isleaf = false;
		up(j, u);
		dp[u] += min(c, dp[j]);
	}

	if (isleaf) {
		dp[u] = 0x3f3f3f3f;
	}
}


void down(int u, int fa) {
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i]; int c = w[i];
		if (j == fa) continue;

		v[j] = min(v[u] + dp[u] - min(c, dp[j]), c);
		if (v[j] == 0) {
			v[j] = c;
		}
		down(j, u);
	}
}

void solve() {
	memset(h, -1, sizeof h);
	memset(dp, 0, sizeof dp);
	memset(v, 0, sizeof v);

	cin >> n;
	for (int i = 2; i <= n; i++) {
		int  a, b, c; cin >> a >> b >> c;
		add(a, b, c); add(b, a, c);
	}

	up(1, -1);
	down(1, -1);

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (dp[i] != 0x3f3f3f3f)
			ans = max(ans, v[i] + dp[i]);
		else
			ans = max(ans, v[i]);
	}

	cout << ans << endl;
}


int main()
{
	int T; cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}