
ZOJ Problem Set  4031
BaoBao is playing a game on a rooted tree with $n$ vertices and $(n1)$ weighted edges. At the beginning of the game, a chess piece is placed on the root of the tree, which is vertex 1. In each step, BaoBao can perform one of the four operations:
The goal of the game is to visit every leaf vertex of the tree using the chess piece. Please help BaoBao calculate the minimum units of value he has to spend to achieve the goal. Recall that a leaf vertex of a tree is a vertex with no child. InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains one integer $n$ ($2 \le n \le 200$), indicating the size of the tree. The following $(n1)$ lines each contains three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$), indicating an edge connecting vertex $u_i$ and vertex $v_i$ with weight $w_i$ in the tree. It's guaranteed that the given graph is a tree, and the sum of $n$ over all test cases will not exceed 2000. OutputFor each test case output one line containing one integer, indicating the minimum units of value BaoBao has to spend to achieve the goal. Sample Input3 8 1 2 1 3 1 1 2 4 2 5 4 2 6 2 2 3 7 3 8 3 3 8 1 2 1 2 3 1 3 4 1 3 5 1 2 6 1 6 7 1 6 8 1 8 1 2 100 2 3 1 3 4 1 3 5 1 2 6 1 6 7 1 6 8 1 Sample Output14 8 107 HintThe trees of the sample test cases are shown above. For the first sample test case, BaoBao should perform the following operations: go to 2, save on 2, go to 4, go to 5, back to save (2), go to 6, back to root (1), go to 3, save on 3, go to 7, back to save (3), go to 8. For the second sample test case, BaoBao should perform the following operations: go to 2, go to 3, save on 3, go to 4, back to save (3), go to 5, back to root (1), go to 2, go to 6, save on 6, go to 7, back to save (7), go to 8. For the third sample test case, BaoBao should perform the following operations: go to 2, save on 2, go to 3, go to 4, back to save (2), go to 3, go to 5, back to save (2), go to 6, save on 6, go to 7, back to save (6), go to 8. Author: WENG, Caizhi Source: The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple 