C. 【GENOIP#41】好难

题目描述

小可可练习完树上邻域数颜色之后，又想出来一个关于树的题拿来问你。

有一颗 $n$ 个点的树和 $n$ 个集合 $S_i$ ，初始时 $S_i = \{ i \}$ 。

有 $q$ 次操作，每次操作分为两种：

• 1 u $(1 \le u \le n)$ ：询问有多少 $v$ 满足 $u \in S_v$ 。
• 2 i $(1 \le i < n)$ ：设输入的第 $i$ 条边为 $(u_i, v_i)$ ，则将 $S_{u_i}, S_{v_i}$ 改为 $S_{u_i} \cup S_{v_i}$ 。

小可可想知道所有 $1$ 操作的答案是什么。

输入格式

第一行两个正整数 $n,q$ ，表示树的大小和操作个数。

接下来 $n-1$ 行每行两个整数 $u_i,v_i$ ，表示树的第 $i$ 条边。

接下来 $q$ 行每行两个整数，表示一次操作。

输出格式

对于每次 $1$ 操作，输出一行一个整数表示对应答案。

样例 1

5 11
1 2
1 3
1 4
1 5
2 4
2 3
2 2
2 1
1 1
1 2
1 3
2 2
2 3
1 4
1 5

5
2
3
4
5

数据范围与提示

样例 2/3

样例下载

数据规模与约定

对于 $20 \%$ 的数据， $n \le 10^3, 1 \le q \le 10^4$ ；

对于另外 $20 \%$ 的数据， $u_i = 1, v_i = i + 1$ ；

对于另外 $20 \%$ 的数据， $u_i = i, v_i = i + 1$ ；

对于 $100 \%$ 的数据， $1 \le n \le 2 \times 10^5, 1 \le q \le 6 \times 10^5$ 。