题目：Water Flow（水流）

问题描述

有一个由节点构成的树，树根是唯一的水源。树中的每条边都有一个最大容量，即单位时间内最多能流过这条边的水量。树的叶子节点（除了树根之外，度数为1的节点）有一个水量需求，即单位时间内需要的水量。

水流从树根流向叶子节点。对于每个非叶子节点（除树根外），流入该节点的总水量必须等于流出该节点的总水量（水流守恒）。树根没有流入水量，其流出的总水量等于所有叶子节点获得的总水量。

你的任务是计算在满足所有边容量限制和水流守恒的前提下，所有叶子节点能够获得的最大总水量。

输入格式

输入包含多组测试用例。

每组测试用例的第一行是一个整数 $n$（2 ≤ n ≤ 200000），表示树的节点数。节点编号为 1 到 $n$，其中 1 号节点是树根。

接下来的 $n-1$ 行，每行包含三个整数 $u$、$v$、$c$，表示一条连接节点 $u$ 和 $v$ 的边，以及这条边的最大容量 $c$（1 ≤ c ≤ 100000）。注意，树是无向的，但水流方向是从父节点到子节点（即从靠近根的节点流向远离根的节点）。

再接下来的 $n$ 行，每行包含一个整数 $d_i$，表示节点 $i$ 的水量需求。对于非叶子节点（除树根外），$d_i$ 必须为 0；对于叶子节点，$d_i$ 是一个正整数；树根的 $d_1$ 没有意义（可以忽略）。

输入以 $n=0$ 结束。

输出格式

对于每组测试用例，输出一个整数，表示所有叶子节点能够获得的最大总水量。

样例输入

3
1 2 1
1 3 1
0
1
1
0

样例输出

2

样例解释

在这个样例中，树有 3 个节点。树根（1号节点）连接两个叶子节点（2号和3号节点），每条边的容量都是 1。两个叶子节点的需求都是 1。由于每条边的容量足够满足对应叶子的需求，总水量为 1+1=2。

source

poj3585 water flow