## CPC '21 Contest 1 P7 - AQT and Quarantine

View as PDF

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem types

AQT is suspicious that brainworms are running wild in DMOJistan! To limit the spread of these IQ-reducing creatures, the admins require that cities of DMOJistan quarantine for a specific amount of time.

DMOJistan can be mapped as a tree with nodes that each represent a city, and edges that represent roads. People can only move between cities by only using the roads. Whenever DMOJ admins orders city to be in quarantine, starting from the beginning of day the node , and its neighbouring cities, form a bubble, where they must quarantine until the end of day . This means that no one inside the bubble can go outside the bubble and vice versa. Note that for any day, we can group cities into disjoint sets of cities where two nodes are in the same set if and only if we can visit each city without violating any of the quarantine rules. For each middle of the day (after the beginning and before the end of the day) from day to day , report the number of such sets.

For all :

For all :

#### Input Specification

The first line is a single integer .

The next lines where the -th line contains and separated by a space representing that there is a direct road between nodes and .

The following line contains and separated by a single space.

The next lines each represent a different type of brainworm, where the -th line contains integers separated by spaces, , and .

#### Output Specification

For each day from to , output the number of such sets described in a problem statement on a new line, where the -th line is the answer of the -th day.

#### Sample Input 1

5
2 3
1 3
4 2
3 5
5 5
2 2 4
4 2 5
5 3 4
5 4 5
3 1 3

#### Sample Output 1

2
5
5
4
3

#### Explanation for Sample 1

At the beginning of day 1, city 3 will form a bubble with its neighbouring cities.

At the middle of day 1, two sets are formed and .

At the end of day 1, nothing happens.

At the start of day 2, city 2 and 4 will form bubbles with their neighbouring cities.

At the middle of day 2, the sets are , , , and .

At the end of day 2, nothing happens.

At the start of day 3, city 5 forms a bubble with its neighbouring cities.

At the middle of day 3, the sets are still , , , and .

At the end of day 3, city 3 and its neighbouring cities will lift their restrictive measures.

At the start of day 4, city 5 will form another bubble with its neighbouring cities.

At the middle of day 4, the sets are , , , .

At the end of day 4, city 5 and its neighbouring cities lift their first bubble restriction but are still in quarantine from their second bubble restriction, and city 2, and its neighbouring cities, lift their quarantine restriction.

At the start of day 5, nothing happens.

At the middle of day 5, the sets are , , .

At the end of day 5, the rest of the restrictions are lifted.

#### Sample Input 2

3
1 2
2 3
3 1
1 1 1
1 1 1
3 1 1

#### Sample Output 2

3

#### Explanation for Sample 2

Note that for the only day, are the sets.