题目背景

Snow has arrived on the farm, and as she does at the beginning of every winter, Bessie is building a snow-cow! Most of the time, Bessie strives to make her sculpture look as much like a real cow as possible. However, feeling artistically inspired, this year she decides to pursue a more abstract route and build a sculpture in the shape of a tree, consisting of $N$ snowballs $(1\le N\le 10^5)$ connected by $N-1$ branches, each connecting a pair of snowballs such that there is a unique path between every pair of snowballs.

Bessie has added a nose to one of the snowballs, so it represents the head of the abstract snow cow. She designates it as snowball number 1. To add more visual interest, she plans to dye some of the snowballs different colors in an artistic fashion by filling old milk pails with colored dye and splashing them onto the sculpture. Colors are identified by integers in the range $1 \ldots 10^5$, and Bessie has an unlimited supply of buckets filled with dyes of every possible color.

When Bessie splashes a snowball with a bucket of dye, all the snowballs in its subtree are also splashed with the same dye (snowball $y$ is in the subtree of snowball $x$ if $x$ lies on the path from $y$ to the head snowball). By splashing each color with great care, Bessie makes sure that all colors a snowball has been splashed with will remain visible. For example, if a snowball had colors $[1,2,3]$ and Bessie splashes it with color $4$, the snowball will then have colors $[1,2,3,4]$.

After splashing the snowballs some number of times, Bessie may also want to know how colorful a part of her snow-cow is. The "colorfulness" of a snowball $x$ is equal to the number of distinct colors $c$ such that snowball $x$ is colored $c$. If Bessie asks you about snowball $x$, you should reply with the sum of the colorfulness values of all snowballs in the subtree of $x.$

Please help Bessie find the colorfulness of her snow-cow at certain points in time.

题目描述

农场下雪啦！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 位整数。

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-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