402589: GYM100814 D Frozen Rivers

In winter, all small rivers of Al-Asi great river in Syria are frozen. But when spring comes back they start to melt. These small rivers are connected to each other exactly like a tree, each river (direct edge in the tree) has a value equal to the amount of ice in it.

Here is the tree of the sample test case:

When rivers start to melt, water starts to flow from node 1 (root of the tree) to any node that it can reach. When the water first reaches a node u, ice starts to melt in all its direct children edges at a rate of 1 unit per second. Once (u, v) edge completely melted, the rate of melting of all other edges that start from u will slow down to be 0.5 unit per second, while the other edges that start from v start melting with 1 unit per second.

Given the rivers tree, and a certain time, can you tell us how many leaves of the tree did the water reach? A leaf is a node that has no children.

The first line contains T the number of test cases. For each test case, the first line contains N the number of nodes (2 ≤ N ≤ 100, 000). Followed by N - 1 lines, each line describes the nodes 2 to N. Each line will contain 2 integers P_i and C_i (1  ≤  P_i ≤ N) (0  ≤  C_i  ≤  100,000) representing the parent of the i-th node (i starts from 2 here) and the amount of ice in the edge connecting the current node to its parent. Node 1 is the root of the tree. After that there is a line contains (1 ≤ Q ≤ 100, 000), the number of queries. Then Q lines contain the times of these queries in seconds (0 ≤  query time  ≤ 10¹²).

Print one line for each query in each test case, this line should contain the number of leaves that the water reached at the time of the query.

1
4
1 3
1 5
2 2
8
1
2
3
4
5
6
7
8

0
0
0
0
1
1
2
2

In the sample test case:

At time 0: water is at node 1

At time 1: water has melted 1 unit of edge (1, 2), and 1 unit of edge (1, 3)

At time 3: water has completely melted edge (1, 2). The rate of melting of (1, 3) drops to 0.5 unit/second, while edge (2, 4) starts to melt at rate 1 unit/second.

At time 5: water has completely melted edge (2, 4), and the remaining edge (1, 3) has 4 units melted, 1 to go.

At time 7: Ice completely melted in all edges.