#196. Accumulation Degree

Accumulation Degree

题目描述

给定一棵正边权树,选择一个顶点作为源点。从源点向其他叶子输送流量,边权表示容量;除源点外各中间点满足流量守恒。求选择最优源点时可输出的最大总流量。树中的叶子指原树度数为1的顶点,源点自身不作为接收点。

输入格式

首行测试组数。每组先输入 n,随后 n−1 行 u、v、c,表示容量为 c 的无向边。

输出格式

每组输出选择最优源点后的最大流量。

样例输入

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

样例输出

26

题意整理;原题与输入输出格式对照。