URI Online Judge | 1782
# Honorable Gift

**Timelimit: 1**

By Duhan Caraciolo, UFPE Brazil

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 ≤ **A** ≤ **N**), **B** (1 ≤ **B** ≤ **N**) 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 **X**_{i} (1 ≤ **X**_{i }≤ 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 |

3 |
Caso #1: 3 6 |