QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
[+1]
Statistics

题面描述

一棵以1为根的树,一共 n 个节点,每一个节点都有颜色,初始时颜色编号都为 1 。

一共进行 m 次操作,操作有两种:

  • 1 x y :把以 x 为根的子树的全部节点染成 y 号颜色。
  • 2 x :询问把连接不同颜色的点的边删掉后,x 所在的连通块大小。边不实际删掉。

输入格式

第一行一个整数 n

接下来 n1 行描述这棵树,每行两个整数 u,v ,表示树上的一条边。

n+1 行一个整数 m

接下来 m 行,每行一个操作,格式如题面所述。

输出格式

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

样例一

input

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

output

5
4
3

explanation

我们用红色表示1,绿色表示2,这是初始的各点颜色,此时询问节点2的答案是5:

这是第一次修改后的树,此时询问节点1的答案是4:

这是第二次修改后的树,此时询问节点5的答案是3:

样例二

input

10
1 2
2 3
1 4
2 5
3 6
2 7
6 8
8 9
9 10
15
1 4 10
1 2 4
1 1 5
1 7 10
1 8 10
2 8
2 2
1 1 5
1 3 4
1 9 9
1 4 6
2 6
2 1
1 4 4
2 2

output

3
6
3
4
4

限制与约定

对于所有数据,1n1061m1061yn

测试点编号 n m 特殊限制
1~6 105 106 n×m108
7~10 105
11~12 106 106 i 的父亲在 [1,i1] 以内随机生成(点1除外)
13~14 5×105 5×105
15 106 106 i 的父亲是 i1(点1除外)
16~20

时间限制:2s

空间限制:1024MB