3542. [POJ 3585]富集程度

【题目描述】

有一个树形的水系，由$n-1$条河道和$n$个交叉点组成。我们可以把交叉点看作树中的节点，编号为$1\sim n$，河道则看作树中的无向边。

每条河道都有一个容量，连接$x$与$y$的河道的容量记为$c(x,y)$。河道中单位时间流过的水量不能超过河道的容量。

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

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

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

【输入格式】

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

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

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

节点编号从1开始。

【输出格式】

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

【样例输入】

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

【样例输出】

26

【样例说明】

A(1)=11+5+8=24

     1->2     11

     1->4->3   5

     1->4->5   8(因为4->3分走了5个流量)

A(2)=5+6=11

     2->1->4->3  5

     2->1->4->5  6

A(3)=5

     3->4->5    5

A(4)=11+5+10=26

     4->1->2    11

     4->3      5

     4->5      10

A(5)=10 

     5->4->1->2  10

【数据规模与约定】

$n\leq 2\times 10^5$

【来源】

《算法竞赛进阶指南》