#1704. 树与染色!
树与染色!
树与染色!
题目描述
标题: 树与染色! - Problem - QOJ.ac
#5168. 树与染色!
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