#P17499. [ICPC 2026 Wuhan I] I Will Always Remember You
[ICPC 2026 Wuhan I] I Will Always Remember You
Problem Description
Given a directed acyclic graph with vertices and edges, and a color sequence of length , where denotes the initial color of vertex .
Let denote the set of all vertices reachable from vertex in graph (including vertex itself).
Now, you need to process operations in order. The operations are of the following two types:
- Given and , change the color of vertex to .
- Given , query the number of distinct colors among all vertices reachable from vertex . That is, find the size of the set .
Input Format
The first line contains two integers (, ), representing the number of vertices and the number of edges in the graph, respectively.
The second line contains integers (), representing the initial color of each vertex.
The next lines each contain two integers (), indicating that there is a directed edge from to in graph . It is guaranteed that graph is a directed acyclic graph (DAG) and contains no multiple edges.
The next line contains an integer (), representing the total number of operations.
The next lines each describe an operation in one of the following two formats:
1 x y: Represents an update operation, changing the color to ().2 x: Represents a query operation, querying the number of distinct colors reachable from vertex ().
Output Format
For each operation of the second type, output a single line containing an integer representing the answer to the query.
9 14
8 4 2 3 5 2 2 4 7
3 5
8 9
4 5
5 8
6 8
3 8
1 4
2 9
2 4
2 8
1 3
7 9
1 8
5 7
10
1 6 4
1 3 3
2 1
2 3
1 4 3
1 8 5
1 8 7
2 7
2 2
2 9
6
5
2
5
1