Tim Jhomas Returns
Output: Standard Output (stdout)
Memory limit: 256 megabytes
Time limit: 2.0 seconds
Tim Jhomas, world-famous secret spy, has infiltrated the sinister K.A.O.S. organization with his network of spies.
There are N spies in his network, numbered from 0 to N-1. Tim Jhomas is spy number 0. Every spy, including Tim Jhomas, has established a two-way connection with one or more other spies. Each spy also has a secret transmitter that can be used once per day - they can use this to send the secret message to one of the spies they have a connection with. Every day, Tim Jhomas wants to pass a secret message around the network to as many spies as possible. Tim starts off by transmitting the message to one of the spies he has a connection with, who can then transmit it along to another spy, and so on.
The connections have been set up so that it's possible for Tim to get the message to any other spy, although not necessarily possible for Tim to get the message to all spies. Additionally, there are a total of N-1 two-way connections in the network. In other words, the connections form a tree.
Tim also wants the message he sends to end up back at himself, so he know the spies have received it. For this reason, every day Tim will choose two spies to add a temporary two-way connection between. The connection is destroyed at the end of the day. If Tim chooses the connection carefully, he can allow the message to be received by the maximum number of spies before being sent back to himself.
However, the sinister K.A.O.S. organization is starting to compromise some of Tim's spies. Every day, for D days, one of his spies gets compromised and becomes permanently unable to send and receive messages. Tim Jhomas will never get compromised because he's too good of a spy. For each day, what is the maximum number of spies in the network (including Tim) that can receive that day's message?
The first line contains two space-separated integers, N and D.
N-1 lines follow. The i-th line contains two space-separated integers, a_i and b_i, stating that there is a two-way connection between the spies a_i and b_i. It is guaranteed that the same connection does not appear twice in the input.
D lines follow. The j-th line contains a single integer k, stating that spy k was compromised permanently on day j. No spy that has already been compromised will be compromised again.
First output a single line, containing the maximum number of spies that can receive the message on the 0-th day (i.e. before any spies have been compromised). Then, for each of the D days, output a single line containing the maximum number of spies that can receive the message on that day (i.e. after a spy has been compromised that day).
For all subtasks:
- 2 \le N \le 50,000
- 0 \le D \le 50,000 and D \le N-2
- 0 \le a_i,b_i \lt N for all i
- 1 \le k \lt N for all days
- On any day it is always possible for Tim to send a message to at least one other spy.
- Subtask 1 (+15%): a_i = i and b_i = i+1 for all connections. In other words, the network of spies forms a line with connections between 0 and 1, 1 and 2, 2 and 3 etc.
- Subtask 2 (+15%): D = 0.
- Subtask 3 (+20%): N <= 1000, D <= 1000.
- Subtask 4 (+25%): There is only one spy that has a two-way connection with Tim Jhomas.
- Subtask 5 (+25%): No further constraints apply.
Before any spies have been compromised, Tim can create a temporary connection between spies 3 and 4. He can then send the message to spy 3, who sends it to spy 4 over the temporary connection, who sends it to spy 1, who then sends it back to spy 0 (Tim). Therefore, a total of 4 spies (including Tim) have received the message.
On the first day spy 2 is compromised. Tim can still use the same strategy as on Day 0 to get the message to 4 spies total.
On the second day spy 4 is also compromised, so he needs to change his strategy. Tim can create a temporary connection between spies 1 and 3. He can then send the message to spy 1, who sends it to spy 3, who sends it back to him. Thus a total of 3 spies can receive the message.
In this explanation \rightarrow means a standard message, \Rightarrow means a temporary connection was used.
Before any spies have been compromised, we can get up to 6 spies by sending the message from 0 \rightarrow 2 \rightarrow 5 \rightarrow 3 \Rightarrow 6 \rightarrow 1 \rightarrow 0
After spy 5 gets compromised, we can only get up to 5 spies by sending the message from 0 \rightarrow 2 \rightarrow 4 \Rightarrow 6 \rightarrow 1 \rightarrow 0
After spy 6 gets compromised, we can only get up to 4 spies by sending the message from 0 \rightarrow 2 \rightarrow 4 \Rightarrow 1 \rightarrow 0
Spy 3 getting compromised doesn't affect our strategy, so 4 spies is still the best we can do
After spy 1 gets compromised, we can only get up to 4 spies by sending the message from 0 \rightarrow 2 \rightarrow 4 \Rightarrow 0
Sample Input 1
5 2 2 1 3 0 0 1 1 4 2 4
Sample Output 1
4 4 3
Sample Input 2
7 4 0 2 3 5 4 2 2 5 0 1 1 6 5 6 3 1
Sample Output 2
6 5 4 4 3