## DMOPC '20 Contest 1 P5 - Victor Takes Over Canada

View as PDF

Points: 17 (partial)
Time limit: 2.2s
Memory limit: 512M

Author:
Problem types

NOW I HAVE THE POWER ~ Victor, 2019

Victor, using the money he earned from selling horseshoe crabs, has managed to buy alien technology!

Using this alien technology, he terraforms Canada into a network of cities, numbered connected by exactly highways. Victor lives in city . He also hires aliens (numbered ) to guard the cities with. As alien guards are expensive, each city has exactly guard assigned to it. An alien can be assigned to multiple cities, but can be present in at most one city at a time (thankfully, these aliens don't teleport).

Over the following minutes, one of the following happens:

• 1 c k: Alien is assigned to guard city , replacing its previous alien guard.
• 2 u: The resistance plans a siege of city and wishes to know the maximum possible number of guards that can come reinforce city .

As the head of intelligence at the resistance, you are tasked with writing a program to calculate these scenarios. A guard is able to reinforce city if and only if lies on the unique path between any one of its assigned cities and city .

If only Victor hadn't been given the roll of paper of power…

#### Constraints

The alien guards are never reassigned.

#### Input Specification

The first line will contain three space-separated integers, , , and .
The second line will contain space-separated integers, , indicating the th alien is assigned to city .
The next lines will each contain a pair of integers, , indicating there is an edge between and .
The next lines will each contain a query.

#### Output Specification

For each expedition, output the maximum possible number of guards that can come reinforce city .

#### Sample Input 1

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

#### Sample Output 1

3
4
2
3

#### Sample Input 2

7 5 4
1 2 3 4 3 2 1
1 2
1 3
1 4
4 5
4 6
4 7
2 4
2 1
2 2
2 7

#### Sample Output 2

4
4
1
1