DMOPC '20 Contest 1 P5 - Victor Takes Over Canada

View as PDF

Submit solution


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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 N cities, numbered 1, \ldots, N connected by exactly N - 1 highways. Victor lives in city 1.
He also hires K aliens (numbered 1, 2, \ldots, K) to guard the cities with. As alien guards are expensive, each city has exactly 1 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 M minutes, one of the following happens:

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

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 u if and only if u lies on the unique path between any one of its assigned cities and city 1.

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

Constraints

For all subtasks, 1 \le K \le N.

Subtask 1 [10%]

1 \leq N, M \leq 2\,000

Subtask 2 [20%]

1\leq N, M\leq 200\,000
The alien guards are never reassigned.

Subtask 3 [40%]

1\leq N, M\leq 200\,000

Subtask 4 [30%]

1\leq N \leq 500\,000, 1 \le M\leq 300\,000

Input Specification

The first line will contain three space-separated integers, N, K, and M.
The second line will contain N space-separated integers, c_1, c_2, \ldots, c_N, indicating the c_ith alien is assigned to city i.
The next N - 1 lines will each contain a pair of integers, a_i, b_i, indicating there is an edge between a_i and b_i.
The next M lines will each contain a query.

Output Specification

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

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

Comments

There are no comments at the moment.