Logo Universal Online Judge

UOJ

时间限制:4 s 空间限制:1024 MB
Statistics

题目描述

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

有一颗 n 个点的树和 n 个集合 Si,初始时 Si = {i}。

有 q 次操作,每次操作分为两种:

• 1 u (1 ≤ u ≤ n):询问有多少 v 满足 u ∈ Sv。

• 2 i (1 ≤ i < n):设输入的第 i 条边为 (ui, vi),则将 Sui, Svi 改为 Sui ∪ Svi。 小可可想知道所有 1 操作的答案是什么。

输入格式

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

接下来 n − 1 行每行两个整数 ui, vi,表示树的第 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

样例输出1

5
2
3
4
5

样例2/3

见下发文件。

数据规模及约定

对于 20% 的数据,n ≤ 10^3, 1 ≤ q ≤ 10^4;

对于另外 20% 的数据,ui = 1, vi = i + 1;

对于另外 20% 的数据,ui = i, vi = i + 1;

对于 100% 的数据,1 ≤ n ≤ 2 × 10^5, 1 ≤ q ≤ 6 × 10^5。