Yet Another Contest 7 P4 - Paparazzi

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 3.0s
Java 4.0s
Python 5.0s
Memory limit: 512M

Problem type

Nils is a celebrity, and the paparazzi are obsessed with taking photos of him!

There are N towns labelled from 1 to N, with N-1 bidirectional roads between them such that it is possible to travel from any town to any other town only using those roads. The i-th road connects towns u_i and v_i. Initially, there is one paparazzo in each town, hoping to get a glimpse of Nils.

Nils will then make M appearances. On the i-th appearance, he will appear in town a_i. Then, each paparazzo will move one town towards Nils. Formally, each paparazzo with move to the unique adjacent town which is closer to a_i than their current town, where distance is defined as the minimum number of roads needed to be travelled to reach one town from another. The exception to this rule is that paparazzi which are already in town a_i will not move.

Note that Nils, being a celebrity, has access to a private jet, and is therefore not bound by the roads. This means that consecutive appearances are not necessarily in adjacent towns. Furthermore, consecutive appearances may be in the same town.

After each appearance, can you determine the number of towns containing at least one paparazzo?


1 \le N, M \le 2 \times 10^5

1 \le u_i, v_i \le N, u_i \ne v_i

Any town can be reached from any other town by only travelling along the roads.

1 \le a_i \le N

Subtask 1 [20%]

1 \le N, M \le 2000

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, N and M.

The i-th of the following N-1 lines contains two space-separated integers, u_i and v_i.

The i-th of the following M lines contains a single integer, a_i.

Output Specification

Output M lines. The i-th line should contain a single integer denoting the number of towns containing at least one paparazzo after the first i appearances.

Sample Input

4 2
1 2
2 3
2 4

Sample Output



After the first appearance in town 1, there are paparazzi in towns 1 and 2 only.

After the second appearance in town 2, all paparazzi are in town 2.


There are no comments at the moment.