「USACO 2019 Platinum」Bessie 的雪牛

题目描述

题目译自 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$