
ZOJ Problem Set  4048
BaoBao has just found a rooted tree with $n$ vertices and $(n1)$ weighted edges in his backyard. Among the vertices, $m$ of them are red, while the others are black. The root of the tree is vertex 1 and it's a red vertex. Let's define the cost of a red vertex to be 0, and the cost of a black vertex to be the distance between this vertex and its nearest red ancestor. Recall that
As BaoBao is bored, he decides to play $q$ games with the tree. For the $i$th game, BaoBao will select $k_i$ vertices $v_{i, 1}, v_{i, 2}, \dots, v_{i, k_i}$ on the tree and try to minimize the maximum cost of these $k_i$ vertices by changing at most one vertex on the tree to a red vertex. Note that
Please help BaoBao calculate the smallest possible maximum cost of the given $k_i$ vertices in each game after changing at most one vertex to a red vertex. InputThere are multiple test cases. The first line of the input is an integer $T$, indicating the number of test cases. For each test case: The first line contains three integers $n$, $m$ and $q$ ($2 \le m \le n \le 10^5$, $1 \le q \le 2 \times 10^5$), indicating the size of the tree, the number of red vertices and the number of games. The second line contains $m$ integers $r_1, r_2, \dots, r_m$ ($1 = r_1 < r_2 < \dots < r_m \le n$), indicating the red vertices. 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 with weight $w_i$ connecting vertex $u_i$ and $v_i$ in the tree. For the following $q$ lines, the $i$th line will first contain an integer $k_i$ ($1 \le k_i \le n$). Then $k_i$ integers $v_{i, 1}, v_{i, 2}, \dots, v_{i, k_i}$ follow ($1 \le v_{i, 1} < v_{i, 2} < \dots < v_{i,k_i} \le n$), indicating the vertices whose maximum cost BaoBao has to minimize. It's guaranteed that the sum of $n$ in all test cases will not exceed $10^6$, and the sum of $k_i$ in all test cases will not exceed $2 \times 10^6$. OutputFor each test case output $q$ lines each containing one integer, indicating the smallest possible maximum cost of the $k_i$ vertices given in each game after changing at most one vertex in the tree to a red vertex. Sample Input2 12 2 4 1 9 1 2 1 2 3 4 3 4 3 3 5 2 2 6 2 6 7 1 6 8 2 2 9 5 9 10 2 9 11 3 1 12 10 3 3 7 8 4 4 5 7 8 4 7 8 10 11 3 4 5 12 3 2 3 1 2 1 2 1 1 3 1 1 1 2 1 2 3 1 2 3 Sample Output4 5 3 8 0 0 0 HintThe first sample test case is shown above. Let's denote $C(v)$ as the cost of vertex $v$. For the 1st game, the best choice is to make vertex 2 red, so that $C(3) = 4$, $C(7) = 3$ and $C(8) = 4$. So the answer is 4. For the 2nd game, the best choice is to make vertex 3 red, so that $C(4) = 3$, $C(5) = 2$, $C(7) = 4$ and $C(8) = 5$. So the answer is 5. For the 3rd game, the best choice is to make vertex 6 red, so that $C(7) = 1$, $C(8) = 2$, $C(10) = 2$ and $C(11) = 3$. So the answer is 3. For the 4th game, the best choice is to make vertex 12 red, so that $C(4) = 8$, $C(5) = 7$ and $C(12) = 0$. So the answer is 8. Author: WENG, Caizhi Source: The 2018 ACMICPC Asia Qingdao Regional Contest, Online 