← 返回题目列表

Codeforces · 620/E

E. 新年树

中文机器翻译题面 查看原题

新年假期结束了,但瑞莎不想扔掉新年树。他邀请了最好的朋友克里姆和古拉尔帮他重新装饰新年树。

新年树是一棵有 n 个顶点、根在顶点 1 的无向树。

您应该处理两种类型的查询:

1.将顶点v的子树中所有顶点的颜色更改为颜色c。
2.求顶点v的子树中不同颜色的数量。

输入

第一行包含两个整数 n, m (1 ≤ n, m ≤ 4·105) — 树中的顶点数和查询数。

第二行包含 n 个整数 ci (1 ≤ ci ≤ 60) — 第 i 个顶点的颜色。

接下来的 n - 1 行中的每一行都包含两个整数 xj, yj (1 ≤ xj, yj ≤ n) — 第 j 条边的顶点。保证您获得正确的无向树。

最后 m 行包含查询的描述。每个描述都以整数 tk (1 ≤ tk ≤ 2) 开始——第 k 个查询的类型。对于第一种类型的查询,后面跟着两个整数 vk, ck (1 ≤ vk ≤ n, 1 ≤ ck ≤ 60) — 其子树将用颜色 ck 重新着色的顶点的编号。对于第二种类型的查询,则遵循整数 vk (1 ≤ vk ≤ n) — 您应该找到其子树的不同颜色数量的顶点数。

输出

对于第二种类型的每个查询,打印整数 a — 查询中给出的顶点的子树中不同颜色的数量。

每个数字都应按照输入中出现的查询顺序打印在单独的行上。

示例

输入 #1

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

输出 #1

2
3
4
5
1
2

输入 #2

23 30
1 2 2 6 5 3 2 1 1 1 2 4 5 3 4 4 3 3 3 3 3 4 6
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
4 11
6 12
6 13
7 14
7 15
7 16
8 17
8 18
10 19
10 20
10 21
11 22
11 23
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4

输出 #2

6
1
3
3
2
1
2
3
5
5
1
2
2
1
1
1
2
3