#3227. 「USACO 2019.12 Platinum」Bessie's Snow Cow

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ksyx

题目描述

题目译自 USACO 2019 December Contest, Platinum Problem 2. Bessie's Snow Cow

农场下雪啦!Bessie 和往年开冬一样在堆雪牛。她之前是个写实派,总是想把他的雪牛堆得和个真牛一样。但今年不一样,受到来自东方的神秘力量的影响,他想来点抽象艺术,因此他想堆成一棵树的样子。这棵树由 N 个雪球, N-1 根树枝构成,每根树枝连接两个雪球,并且每两个雪球之间路径唯一。

Bessie 要给他的雪牛来点细节。因此他给其中一个雪球加了个鼻子,来表示这是他那抽象的牛的头,并且把它称作雪球 1 。为了让雪牛更好看,他还要给某些雪球来点不同的颜色。于是,他用旧牛奶桶装满了颜料泼到雪牛上。这些颜料分别被编号为 1\ldots 10^5 ,且每种颜色都无限量供应。

当 Bessie 把一桶颜料泼到一个雪球上时,这个雪球子树上的所有雪球也会被染色(我们称雪球 y 在雪球 x 的子树里当且仅当雪球 x 处在雪球 y 到雪球 1 的路径上)。Bessie 有着精确的泼颜料技术,因此在泼完一种颜料后,一个雪球上之前被染过的所有颜色依然清晰可见。例如,一个雪球之前显现出来颜色 [1,2,3] ,然后 Bessie 把装有 4 号颜色的牛奶桶泼上去,那么这个雪球将显现出来颜色 [1,2,3,4] 。 在泼了几桶颜料以后,Bessie 可能想要了解它的雪牛有多五彩斑斓。令雪球 x 的『颜色丰富度』为这个雪球被染上的不同颜色总数 c ,当 Bessie 想了解雪球 x 的相关信息时,你应该回答他雪球 x 的子树中所有的雪球的颜色丰富度之和。

救救孩子吧!

输入格式

第一行, N 和询问数 Q

接下来 N-1 行每行两个用空格隔开的数 a b ,表示雪球 a b 中间有一根树枝相连。

最后 Q 行每行一个请求,格式及对应含义如下:

  • 1 x c(修改):表示 Bessie 把一桶装有颜色 c 的颜料泼到雪球 x ,使得其子树上所有雪球被染色。
  • 2 x(询问):询问雪球 x 的子树的颜色丰富度之和。

输出格式

对于每个询问,输出所询问子树的颜色丰富度之和。为了防止溢出,你需要使用 64 位整数。

样例

样例输入

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

样例输出

1
0
1
1
0
2
0
2
1
1
5
1
3
1
1

样例解释

执行完第一个修改后雪球 4 被染上了颜色 1

执行完第二个修改后雪球 4 和雪球 5 被染上了颜色 2

执行完第三个修改后所有雪球都被染上了颜色 1

数据范围与提示

对于测试点 2,3 1\le N\le 10^2,\ 1\le Q\le 2\times 10^2

对于测试点 4\sim 6 1\le N\le 10^3,\ 1\le Q\le 2\times 10^3

对于 100\% 的数据, 1\le N,\ Q,\ c \le 10^5,\ 1\le a,\ b,\ x \le N