26429번 - Water Container System 서브태스크다국어

문제

There is a water container system with $\mathbf{N}$ identical containers, which can be represented as a tree, where each container is a vertex. The containers are connected to each other with $\mathbf{N}-1$ bidirectional pipes. Two containers connected to each other are always placed on adjacent levels. Formally, if two containers $a$ and $b$ are connected to each other, then $|level_a - level_b | = 1$. Container 1ドル$ is placed at the bottommost level. Each container is connected to exactly one container on the level below (the only exception is container 1ドル,ドル 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 1ドル$ liter, and initially all the containers are empty. Assume that the pipe has a capacity of 0ドル$ 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:

The first level of the system consists of a single container, container 1ドル$ (root). Container 1ドル$ is connected to container 2ドル$ and container 3ドル,ドル which are present in the above level, level 2ドル$. Container 2ドル$ is also connected to container 4ドル,ドル which is present at level 3ドル$.

You are given $\mathbf{Q}$ queries. Each query contains a single integer $i$ which represents a container. For each query, add an additional 1ドル$ liter of water in container $i$.

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

In step 1ドル,ドル after adding 1ドル$ liter of water in container 3ドル,ドル the water flows downward because the water containers at the lower level are still empty.

In step 2ドル,ドル after adding 1ドル$ liter of water in container 3ドル,ドル the water flows downward, but as the container 1ドル$ is already filled completely, the water is distributed evenly between water containers 2ドル$ and 3ドル$.

In step 3ドル,ドル after adding 1ドル$ liter of water in container 3ドル,ドル the water containers 2ドル$ and 3ドル$ are completely filled.

In step 4ドル,ドル after adding 1ドル$ liter of water in container 3ドル,ドル the water is pushed up to water container 4ドル,ドル 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.

입력

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

The first line of each test case contains the two integers $\mathbf{N}$ and $\mathbf{Q},ドル where $\mathbf{N}$ is the number of containers and $\mathbf{Q}$ is the number of queries.

The next $\mathbf{N}-1$ lines contain two integers $i$ and $j$ (1ドル \le i, j \le \mathbf{N},ドル and $i ≠ j$) meaning that the $i$-th water container is connected to the $j$-th water container.

Each of the next $\mathbf{Q}$ lines contain a single integer $i$ (1ドル \le i \le \mathbf{N}$) that represents the container to which 1ドル$ liter of water should be added.

출력

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

제한

• 1ドル \le \mathbf{T} \le 100$.
• 1ドル \le \mathbf{Q} \le \mathbf{N}$.
• It is guaranteed that the given water container system is a tree.

Test Set 1 (6점)

시간 제한: 20 초

• 1ドル \le \mathbf{N} \le 65535$.
• The water container system is a perfect binary tree.

Test Set 2 (9점)

시간 제한: 60 초

• 1ドル \le \mathbf{N} \le 10^4$.

힌트