Bessie's Snow Cow

题目描述:

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

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

当 Bessie 把一桶颜料泼到一个雪球上时，这个雪球子树上的所有雪球也会被染色（我们称雪球 y 在雪球 x 的子树里当且仅当雪球 x 处在雪球 y 到雪球 1 的路径上）。Bessie 有着精确的泼颜料技术，因此在泼完一种颜料后，一个雪球上之前被染过的所有颜色依然清晰可见。例如，一个雪球之前显现出来颜色[1,2,3]，然后 Bessie 把装有 4 号颜色的牛奶桶泼上去，那么这个雪球将显现出来颜色[1,2,3,4]。 在泼了几桶颜料以后，Bessie 可能想要了解她的雪牛有多五彩斑斓。令雪球 x 的『颜色丰富度』为这个雪球被染上的不同颜色总数 ，当 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≤N≤10²,1≤Q≤2×10²；

对于测试点 4−6，1≤N≤10³,1≤Q≤2×10³；

对于 100% 的数据，1≤N, Q, c≤10⁵,1≤a, b, x≤N。

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2019 DEC Platinum