3358. [USACO19 Dec Platinum]Bessie’s Snow Cow

【题目描述】

本题面由 @数声风笛 翻译。

雪已经降落在农场上了，Bessie 像每个冬天初一样，正在筑雪牛！大多数时候，Bessie 都在努力使自己的雕塑看起来尽可能像一头真正的牛。然而，由于受到艺术启发，今年她决定走一条更抽象的路线，并以树形建造雕塑，由 $N - 1$ 个分支相连的 $N$ 个雪球 $( 1 ≤ N ≤ 10^5 )$ 组成，每个分支连接一对雪球，每对雪球之间都有一条独特的路径。

Bessie 在其中一个雪球上加了一个鼻子，因此它代表了抽象雪牛的头。她将其指定为雪球编号 $1$ 。为了增加视觉趣味，她计划通过以艺术方式将旧的牛奶桶装满彩色染料并将其溅到雕塑上，从而将一些雪球染成不同的颜色。颜色由范围为 $1 … 10^5$ 的整数标识，Bessie 可以提供无限数量的桶，桶中装有每种可能的颜色的染料。

当 Bessie 用一桶染料将雪球溅起时，其子树中的所有雪球也都被相同的染料溅起（雪球 $y$ 在雪球 $x$ 的子树中，如果 $x$ 位于从 $y$ 到头部雪球的路径上）。通过仔细地溅起每种颜色，Bessie 确保了溅到雪球上的所有颜色都将保持可见。例如，如果雪球的颜色为 $[1,2,3]$ ，而 Bessie 用颜色 $4$ 飞溅它，则雪球的颜色为 $[1,2,3,4]$ 。 

在把雪球溅了好几次之后，Bessie 可能还想知道她的雪牛部分有多彩色。雪球 $x$ 的“色彩度”等于不同颜色 $c$ 的数量，以使雪球 $x$ 上色 $c$ 。如果 Bessie 向你询问有关雪球 $x$ 的问题，则应使用 $x$ 子树中所有雪球的彩度值之和进行回答。 

请帮助 Bessie 在某些时间点找到她雪牛的色彩。

【输入格式】

第一行包含 $N$ ，查询数量 $Q$ $( 1 ≤ Q ≤ 10^5 )$。

接下来的 $N - 1$ 行分别包含两个以空格分隔的整数 $a$ 和 $b$，描述了连接雪球 $a$ 和 $b$ $( 1 ≤ a , b ≤ N )$ 的分支。 

最后的 $Q$ 行各包含一个查询。

查询 $1$ $x$ $c$ 

表示 Bessie 在雪球 $x$ 上洒了一桶颜色为 $c$ 的果汁，为 $x$ 子树中的所有雪球上色。

查询 $2$ $x$ 

是对 $x$ 子树中所有雪球的色彩值求和的查询。

显然， $1 ≤ x ≤ N$ 和 $1 ≤ c ≤ 10^5$。

【输出格式】

对于类型2的每个查询，在相应的子树中打印色彩值的总和。

请注意，应使用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$ 。

在第二次查询类型1之后，雪球4和5被染成颜色 $1$ 。

在类型1的第三个查询之后，所有雪球都用颜色 $1$ 染色。

【提示】

对于$ 21\% $的测试数据(测试点$ 1\sim3 $)，满足$ N ≤ 10^2,Q ≤ 2 × 10^2 $。

对于$ 43\% $的测试数据(测试点$ 1\sim6 $)，满足$ N ≤ 10^3,Q ≤ 2 × 10^3 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 十二月公开赛 Platinum 组