#1704. 树与染色!

    ID: 1704 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1056来源:qoj.ac数据:公开样例并查集线段树

树与染色!

树与染色!

题目描述

标题: 树与染色! - Problem - QOJ.ac

#5168. 树与染色!

Statistics

The problem was used in the following contests:

题面描述

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

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

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

输入格式

第一行一个整数 n 。

接下来 n−1 行描述这棵树,每行两个整数 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

限制与约定

对于所有数据,1≤n≤106 ,1≤m≤106 ,1≤y≤n 。

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

时间限制:2s

空间限制:1024MB

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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

样例 2

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
3
6
3
4
4