7610번 - Synchronization 서브태스크다국어

The JOI Co., Ltd. has N servers in total around the world. Each server contains an important piece of information. Different servers contain different pieces of information. The JOI Co., Ltd. is now building digital lines between the servers so that the pieces of information will be shared with the servers. When a line is built between two servers, pieces of information can be exchanged between them. It is possible to exchange pieces of information from one server to another server which is reachable through the lines which are already built.

Each server has a high-performance synchronization system. When two servers can exchange pieces of information each other and they contain different pieces of information, they automatically synchronize the pieces of information. After a synchronization between the server A and the server B, both of the servers A and B will contain all the pieces of information which are contained in at least one of the servers A and B before the synchronization.

In order to reduce the cost, only N − 1 lines can be built. After the N − 1 lines are built, there will be a unique route to exchange pieces of information from one server to another server without passing through the same server more than once.

In the beginning (at time 0), no lines are built. Sometimes, lines are built in a harsh condition (e.g. in a desert, in the bottom of sea). Some of the lines become unavailable at some point. Once a line becomes unavailable, it is not possible to use it until it is rebuilt.

It is known that, at time j (1 ≤ j ≤ M), the state of exactly one line is changed.

We need to know the number of different pieces of information contained in some of the servers at time M + 1.

Write a program which, given information of the lines to be built and the state of the lines, determine the number of different pieces of information contained in some of the servers

Read the following data from the standard input.

• The first line of input contains three space separated integers N, M, Q. This means the number of the servers is N, a list of M changes of the state of the lines is given, and we need to know the number of different pieces of information contained in Q servers.
• The i-th line (1 ≤ i ≤ N − 1) of the following N − 1 lines contains space separated integers X_i, Y_i. This means the line i, when it is built, connects the server X_i and the server Y_i.
• The j-th line (1 ≤ j ≤ M) of the following M lines contains an integer D_j. This means the state of the line D_j is changed at time j. Namely, if the line D_j is unavailable just before time j, this line is built at time j. If the line D_j is available just before time j, this line becomes unavailable at time j. When the state is changed at time j, all the synchronization processes will be finished before time j + 1.
• The k-th line (1 ≤ k ≤ Q) of the follwing Q lines contains an integer C_k. This means we need to know the number of different pieces of information contained in the server C_k in the end.

Write Q lines to the standard output. The k-th line (1 ≤ k ≤ Q) should contain an integer, the number of different pieces of information contained in the server C_k in the end.

• 2 ≤ N ≤ 100 000.
• 1 ≤ M ≤ 200 000.
• 1 ≤ Q ≤ N.
• 1 ≤ X_i ≤ N, 1 ≤ Y_i ≤ N, X_i ≠ Y_i (1 ≤ i ≤ N − 1).
• 1 ≤ D_j ≤ N − 1 (1 ≤ j ≤ M).
• 1 ≤ C_k ≤ N (1 ≤ k ≤ Q).
• The values of C_k are distinct.
• If all of the lines are built, there will be a route from one server to another server through the lines.

In the beginning, we assume the server i (1 ≤ i ≤ 5) contains the piece i of information.

• At time 1, the line 1 is built and the servers 1, 2 become connected. Then, both of the servers 1, 2 contain the pieces 1, 2 of information.
• At time 2, the line 2 is buil, and the server 1, 3 become connected. Including the line 1, the servers 1, 2, 3 are connected. The servers 1, 2, 3 contain the pieces 1, 2, 3 of information.
• At time 3, the line 1 becomes unavailable because it was available just before this moment.
• At time 4, the line 4 is built and the servers 2, 5 become connected. Both of the servers 2, 5 contain the pieces 1, 2, 3, 5 of information. Note that the servers 1, 2 can not exchange pieces of information each other because the line 1 became unavailable.
• At time 5, the line 4 becomes unavailable.
• At time 6, the line 3 is built and the servers 2, 4 become connected. Then, both of the servers 2, 4 contain the pieces 1, 2, 3, 4, 5 of information.

As explained above, in the end, the servers 1, 4, 5 have 3, 5, 4 different pieces of information, respectively.