URI Online Judge | 1782

Honorable Gift

By Duhan Caraciolo, UFPE BR Brazil

Timelimit: 1

Guga won a connected graph for his birthday, with N nodes and N-1 bidirectional edges. Each edge has a weight and connects two nodes. When Andre found out about Guga’s gift, he came up with the following game: Given an integer X, how many pairs (A,B) (A ≤ B) exist such that all edges of the shortest path from node A to node B have weight less than or equal to X?

Now Guga and Andre need a program to answer a lot of these questions, so they can play indefinitely and know whether they got the right answer.


The first line of input contains an integer T (1 ≤ T ≤ 50), the number of test cases. The first line of each test case contains N (1 ≤ N 10⁵), the number of nodes in Guga’s graph. Each of the following N-1 lines contains three integers A (1 ≤ AN), B (1 ≤ BN) and C (1 ≤ C ≤ 10⁶), indicating that there is an edge from node A to node B with weight C. The next line contains an integer Q (1 ≤ Q ≤ 10⁴), the number of times that Guga and Andre will play. The following line contains Q integers Xi (1 ≤ Xi ≤ 10⁶), the greatest weight allowed in the shortest path, as explained above.


For each test case print “Caso #X:”, where X is the number of the current case, starting at 1, followed by the answers for each of the Q queries of this test case preceded by a single space.

Input Sample Output Sample

1 2 2
1 3 2
1 2
1 2 3
2 3 5
3 4 7
1 10

Caso #1: 3 6
Caso #2: 7
Caso #3: 1 1