P5852 [USACO19DEC] Bessie's Snow Cow P

农场下雪啦！Bessie 和往年开冬一样在堆雪牛。她之前是个写实派，总是想把她的雪牛堆得和个真牛一样。但今年不一样，受到来自东方的神秘力量的影响，她想来点抽象艺术，因此她想堆成一棵树的样子。这棵树由 $N$ 个雪球，$N-1$ 根树枝构成，每根树枝连接两个雪球，并且每两个雪球之间路径唯一。 Bessie 要给她的雪牛来点细节。因此她给其中一个雪球加了个鼻子，来表示这是他那抽象的牛的头，并且把它称作雪球 $1$。为了让雪牛更好看，她还要给某些雪球来点不同的颜色。于是，她用旧牛奶桶装满了颜料泼到雪牛上。这些颜料分别被编号为 $1,2,\dots 10^5$，且每种颜色都无限量供应。 当 Bessie 把一桶颜料泼到一个雪球上时，这个雪球子树上的所有雪球也会被染色（我们称雪球 $y$ 在雪球 $x$ 的子树里当且仅当雪球 $x$ 处在雪球 $y$ 到雪球 $1$ 的路径上）。Bessie 有着精确的泼颜料技术，因此在泼完一种颜料后，一个雪球上之前被染过的所有颜色依然清晰可见。例如，一个雪球之前显现出来颜色 $\left[ 1,2,3 \right]$，然后 Bessie 把装有 $4$ 号颜色的牛奶桶泼上去，那么这个雪球将显现出来颜色 $\left[ 1,2,3,4 \right]$。 在泼了几桶颜料以后，Bessie 可能想要了解她的雪牛有多五彩斑斓。令雪球 $x$ 的『颜色丰富度』为这个雪球被染上的不同颜色总数 ，当 Bessie 想了解雪球 $x$ 的相关信息时，你应该回答她雪球 $x$ 的子树中所有的雪球的颜色丰富度之和。 救救孩子吧！

第一行，$N$ 和询问数 $Q$。 接下来 $N-1$ 行每行两个用空格隔开的数 $a$ 和 $b$，表示雪球 $a$ 和 $b$ 中间有一根树枝相连。 最后 $Q$ 行每行一个请求，格式及对应含义如下： - `1 x c`（修改）：表示 Bessie 把一桶装有颜色 $c$ 的颜料泼到雪球 $x$ ，使得其子树上所有雪球被染色。 - `2 x`（询问）：询问雪球 $x$ 的子树的颜色丰富度之和。

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

#### 样例解释 执行完第一个修改后雪球 $4$ 被染上了颜色 $1$。 执行完第二个修改后雪球 $4$ 和雪球 $5$ 被染上了颜色 $2$。 执行完第三个修改后所有雪球都被染上了颜色 $1$。 #### 数据范围 对于测试点 $2,3$，$1\le N\le 10^2,1\le Q\le 2\times 10^2$； 对于测试点 $4-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$。 USACO 2019 December 铂金组T2