#198. 积蓄程度

积蓄程度

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

题目描述

有一个树形的水系,由 N1\red {N-1} 条河道和 N\red {N} 个交叉点组成。

我们可以把交叉点看作树中的节点,编号为 1N\red {1\sim N},河道则看作树中的无向边。

每条河道都有一个容量,连接 x\red {x}y\red { y} 的河道的容量记为c(x,y)\red { c(x,y)}

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

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

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

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

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

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

整个水系的流量就定义为源点单位时间发出的水量。

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

输入格式

输入第一行包含整数T\red T,表示共有T\red {T}组测试数据。

每组测试数据,第一行包含整数N\red {N}

接下来N1\red {N-1}行,每行包含三个整数x,y,z\red {x,y,z},表示xy\red {x,y}之间存在河道,且河道容量为z\red {z}

节点编号从1\red {1}开始。

输出格式

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

数据保证结果不超过2311\red {2 ^{31} −1}

样例

输入样例

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

输出样例

26

提示

N2×105\red {N≤2\times 10^5}

DP

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-11-18 14:10
结束于
2023-11-18 16:58
持续时间
2.8 小时
主持人
参赛人数
8