该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

0x50 动态规划（0x54 树形DP）例题3：积蓄程度[POJ3585]

【题意】

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

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

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

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

整个水系的流量就定义为源点单位时间发出的水量。求哪个点作为源点时，整个水系的流量最大，输出这个最大值。

【输入格式】

第一行一个整数 $T$ ，表示共有 $T$ 组测试数据。每组数据描述如下：

第一行一个整数 $N$（$N \le 2 \times 10^5$ ）。

下来 $N-1$ 行，每行包含三个整数 $x \ y \ c$（$1 \le x,y \le N$），表示节点 $x$ 和节点 $y$ 之间直接相连的河道容量为 $c$ 。

【输出格式】

每组数据输出一行一个整数，表示水系流量的最大值。

数据保证结果不超过 $2^{31}−1$。

【输入样例】

1
5
1 2 11
1 4 13
3 4 5
4 5 10

【输出样例】

26