Water Container System solution kickstart

There is a water container system with NN identical containers, which can be represented as a tree, where each container is a vertex. The containers are connected to each other with N1N−1 bidirectional pipes. Two containers connected to each other are always placed on adjacent levels. Formally, if two containers aa and bb are connected to each other, then |levelalevelb|=1|levela−levelb|=1. Container 11 is placed at the bottommost level. Each container is connected to exactly one container on the level below (the only exception is container 11, which has no connections below it), but can be connected to zero or more containers on the level above. The maximum capacity of each container is 11 liter, and initially all the containers are empty. Assume that the pipe has a capacity of 00 liters. In other words, they do not store any water, but only allow water to pass through them in any direction.

Consider the following diagram which is an example of a water container system:

Water Container System solution kickstart

The first level of the system consists of a single container, container 11 (root). Container 11 is connected to container 22 and container 33, which are present in the above level, level 22. Container 22 is also connected to container 44, which is present at level 33.

You are given QQ queries. Each query contains a single integer ii which represents a container. For each query, add an additional 11 liter of water in container ii.

The following diagram illustrates the flow of the water in the system in different conditions:

In step 11, after adding 11 liter of water in container 33, the water flows downward because the water containers at the lower level are still empty.
In step 22, after adding 11 liter of water in container 33, the water flows downward, but as the container 11 is already filled completely, the water is distributed evenly between water containers 22 and 33.
In step 33, after adding 11 liter of water in container 33, the water containers 22 and 33 are completely filled.
In step 44, after adding 11 liter of water in container 33, the water is pushed up to water container 44, which is then completely filled.

As illustrated in the example above, containers at the same level will have the same amount of water. Find the number of water containers that are completely filled after processing all the queries.

Water Container System solution kickstart

Input

The first line of the input gives the number of test cases, TTTT test cases follow.
The first line of each test case contains the two integers NN and QQ, where NN is the number of containers and QQ is the number of queries.
The next N1N−1 lines contain two integers ii and jj (1i,jN1≤i,j≤N, and iji≠j) meaning that the ii-th water container is connected to the jj-th water container.
Each of the next QQ lines contain a single integer ii (1iN1≤i≤N) that represents the container to which 11 liter of water should be added.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the number of water containers that are completely filled after processing all the queries.

Water Container System solution kickstart

Memory limit: 1 GB.
1T1001≤T≤100.
1QN1≤Q≤N.
It is guaranteed that the given water container system is a tree.

Test Set 1

Time limit: 20 seconds.
1N655351≤N≤65535.
The water container system is a perfect binary tree.

Test Set 2

Time limit: 60 seconds.
1N1041≤N≤104.

Water Container System solution kickstart

Note: there are additional samples that are not run on submissions down below.

Sample Input
2
1 1
1
3 2
1 2
1 3
1
2

Sample Output
Case #1: 1
Case #2: 1

In Sample Case #1, there is N=1N=1 water container. The number of completely filled water containers after adding 11 liter of water in container 11 is 11.

In Sample Case #2, there are N=3N=3 water containers. The number of completely filled water containers after processing all the queries is 11.

After adding 11 liter of water in container 11: container 11 is completely filled, and the remaining containers are empty.
After adding 11 liter of water in container 22: container 11 is completely filled, and containers 22 and 33 are partially filled.

Water Container System solution kickstart

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input
2
4 4
1 2
1 3
2 4
3
3
3
3
5 2
1 2
5 3
3 1
2 4
4
5

Sample Output
Case #1: 4
Case #2: 1

In Sample Case #1, there are N=4N=4 water containers. The number of completely filled water containers after processing all the queries is 44, which is already explained in the problem statement.

In Sample Case #2, there are N=5N=5 water containers. The number of completely filled water containers after processing all the queries is 11.

After adding 11 liter of water in container 44: container 11 is completely filled, and the remaining containers are empty.
After adding 11 liter of water in container 55: container 11 is completely filled, containers 22 and 33 are partially filled, and the remaining containers are empty.