#P17499. [ICPC 2026 Wuhan I] I Will Always Remember You
[ICPC 2026 Wuhan I] I Will Always Remember You
题目描述
给定一个 个点 条边的有向无环图 ,以及一个长度为 的颜色序列 ,其中 表示点 的初始颜色。
记 表示在图 上从点 出发能够到达的所有点构成的集合(包括点 自身)。
现在需要依次处理 次操作,操作分为以下两种:
- 给定 和 ,将点 的颜色 修改为 。
- 给定 ,查询从点 出发能够到达的所有点中,一共有多少种不同的颜色。即求集合 的大小。
输入格式
第一行包含两个整数 (,),分别表示图的节点数和边数。
第二行包含 个整数 (),表示每个节点的初始颜色。
接下来 行,每行包含两个整数 (),表示图 中存在一条从 指向 的有向边。保证图 是一个有向无环图,且不存在重边。
接下来一行包含一个整数 (),表示操作的总次数。
接下来 行,每行描述一次操作,格式为以下两种之一:
1 x y:表示一次修改操作,将 的颜色修改为 ()。2 x:表示一次查询操作,查询从点 ()出发能到达的颜色种类数。
输出格式
对于每个第二种操作,输出一行包含一个整数,表示对应查询的答案。
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