问题1159--后花园的树

1159: 后花园的树

[命题人 : ]
时间限制 : 2.000 sec  内存限制 : 256 MB

题目描述

菜哭武的后花园里种着一棵树,这棵树有n个节点和n-1条边,每个节点都涂着一种颜色。菜哭武打算在接下来的m天里,每天执行以下两个操作之一:

1.菜哭武选择某一种颜色和树上的某一个节点,将这个节点涂上这种颜色(会将该节点原有的颜色覆盖)
2.菜哭武选择一种颜色,然后询问这棵树上由所有涂着这种颜色的节点构成的子树含有多少个节点,(原树上的某个点集S构成的子树T的定义是:
如果u∈S,v∈S,那么原树u和v路径上的所有点都属于这棵子树T)。如果这棵树上没有这种颜色的节点,那么定义询问的结果为0。

输入

第1行两个整数n和m(1 <= n, m <= 105) ,分别代表树的节点个数和天数。
第2行到第n行,每行两个整数u和v(1<= u, v <= n), 代表节点u和v之间有一条边
第n + 1行有n个整数,用空格隔开,第i个数代表节点i初始涂的颜色ci(1 <= ci <= n)
接下来m行,每行开头一个数op,代表操作的类型。op = 1代表涂色,op = 2代表询问。
若op = 1,接下来会有两个整数x和y(1 <= x, y <= n),代表将节点x涂成颜色y
若op = 2,接下来会有一个整数x, 代表询问颜色为x的节点构成子树含有的节点个数。

输出

对于每一个op = 2的操作,输出一行整数,代表询问的结果。

样例输入 Copy

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

样例输出 Copy

4
0
1
1

来源/分类