Flow on Tree
当前没有测试数据。
Mr. Kaboom has recently learned about maximum flow. Now his friend Mr. Taboom gave him this problem.
You are given a tree with N vertices. The vertices are numbered from 1 to N. Each edge of the tree has some capacity associated with it. Between each pair of vertices there is only one way to go. Now imagine for each pair of vertices that one of the vertex is the source and the other is the sink. Then Mr. Kaboom needs to find out what is the maximum flow for each pair of vertices. Mr. Taboom decides to reduce Mr. Kaboom's misery and asked him to provide the sum of maximum flow between all possible pair of vertices. Mr. Kaboom has found no solution and has trusted you with this task. Can you save his day?
Input
The very first line of the input will contain the number of test cases T. Then T tests follow. First line of each test contains N, the number of vertices in the tree. The next N-1 lines each contain three integers. The first two integers denotes the vertices this edge connects. The third integer gives the capacity of the edge.
Output
Constraints
- 1≤ T ≤ 20
- 1≤ N≤105
- Capacities of each edge will be non-negative and no more than 106.
- The total number of vertices among all test cases will be less than 5*105
The total number of vertices among all test cases will be less than 500000.
Sample Input
2
4
1 2 5
1 3 2
1 4 3
3
1 2 5
2 3 6
Output:
34
32
Explanation:
For the first case, the maximum flow for each pair is,
For the second case, the maximum flow for each pair is,
Problem-setter: Nafis Sadique