Colored Tree

题目描述

给定一棵以 $1$ 号点为根的树，树上每个点都有一个颜色。

对于一个点 $u$，称以 $u$ 为根的子树中出现过的不同颜色数量为 $D_u$。

现在需要支持两种操作：

• 1 u c：将点 $u$ 的颜色修改为 $c$；
• 2 k：询问当前有多少个点 $u$ 满足 $D_u=k$。

对于每个 2 k 操作，输出答案。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含两个整数 $N,Q$，分别表示树的点数和操作数。

接下来 $N-1$ 行，每行两个整数 $u,v$，表示树上有一条无向边连接 $u$ 和 $v$。

接下来一行包含 $N$ 个整数，第 $i$ 个整数表示点 $i$ 的初始颜色。

接下来 $Q$ 行，每行表示一个操作，格式为以下两种之一：

• 1 u c：将点 $u$ 的颜色修改为 $c$；
• 2 k：询问当前有多少个点的子树中恰好有 $k$ 种不同颜色。

输出格式

对于每个 2 k 操作，输出一行一个整数，表示答案。

数据范围

对于本题数据，满足：

• $1 \le T \le 5$；
• $1 \le N,Q \le 10^5$；
• $1 \le u,v \le N$；
• 输入图保证是一棵树；
• 根节点固定为 $1$；
• 颜色编号为正整数，且不超过 $10^5$；
• 对于操作 1 u c，$1 \le u \le N$，$1 \le c \le 10^5$；
• 对于操作 2 k，$1 \le k \le 100$。

样例输入

1
3 2
1 2
2 3
1 2 3
1 2 1
2 2

样例输出

2

样例说明

初始时，点 $1$ 的子树颜色集合为 $\{1,2,3\}$，点 $2$ 的子树颜色集合为 $\{2,3\}$，点 $3$ 的子树颜色集合为 $\{3\}$。

执行 1 2 1 后，三点颜色变为 $1,1,3$。

此时点 $1$ 的子树颜色集合为 $\{1,3\}$，点 $2$ 的子树颜色集合为 $\{1,3\}$，点 $3$ 的子树颜色集合为 $\{3\}$。

所以恰好含有 $2$ 种不同颜色的子树有 $2$ 个。