源点树

题目描述:

现在有一个无根树。该树有以下规定：

    ·  有且仅有一个点为源点，可以释放无限多的水量。

    ·  而每条都有一个容量，通过该边的水量不能超过该边的容量。

    ·  仅有输入水量而没有输出水量的节点，称为终端，终端可以容纳无限大的水量。

    ·  每个节点都不会存留水量。

下面是一个例子：

若以1为源点，最大总共能释放24的水量，因为：

1节点-》2节点，最大可以释放11的水量，若1节点-》2节点释放12的水量，就会超过该边容量，不符合规则。

1节点-》3节点，最大可以释放13的水量，若1节点-》3节点释放15的水量，就会超过该边容量，不符合规则。

此时3节点向4,5节点释放的总水量为13，因为流入3节点的总水量只有13.

现给定一棵树，求以哪个节点为源点释放的总水量最大。

输入格式:

输入有多组数据，第一行是数据组数T（T<=10）。

接下来每组数据，开头是一个数n，表示该无根树的节点数。

接下来n-1行，每行三个整数a,b,c，表示有一个水道连接a，b两节点，流量为c。

输出格式:

 一共T行，每行输出对应数据的最大流量，不需要输出以哪个节点作为源点。

样例输入:

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

样例输出:

26

提示:

对于30%的数据，T=1，n<=100，max(c)<=100.

对于60%的数据，T<=5，n<=5000，max(c)<=500.

对于100%的数据，T<=10，n<=200000,max(c)<=1000.

样例解释：

选节点4为源点流量最大。

本题数据较大，时间限制也较大。

本题数据由zhr1502随机生成，未经允许，不得纂改！！

时间限制: 6000ms
空间限制: 256MB

---

来源: by zhr