#2582. 二次扫描与换根

二次扫描与换根

Description

aa ((xx ))表示树中节点xx 的累积度,定义如下:

①树的每个边都有一个正容量;

②树中度为11的节点叫作终端;

③每条边的流量都不可以超过其容量;

aa ((xx ))是节点xx 可以流向其他终端节点的最大流量。

示例如下图所示。 image

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

image

2a(2)=5+6=11(2)a (2)=5+6=11

image

3a(3)=5(3)a (3)=5

image

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

image

5a(5)=10(5)a (5)=10

image

树的累积度是树中节点的最大累积度。

Input

11行是一个整数tt ,表示测试用例的数量。每个测试用例的第11行都是一个正整数nn ,表示节点数,节点编号为11nn 。下面nn -11行中的每一行都包含三个整数xxyyzz ,表示在节点xx 和节点yy 之间有一条边容量为zz 。所有元素都是不超过220000000000的非负整数。

Output

对每个测试用例,都单行输出树的累积度。

Samples

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

来源

POJ3585