TouchStone
请登录后使用
系统首页 　练习题库 　考试列表 　判题结果 　信息发布 　解题排行
P6555【USACO 2019 Dec Platinum】Bessie's Snow Cow
 限制 : 时间限制 : 10000 MS   空间限制 : 565536 KB 评测说明 : 1s,512m
###### 问题描述

Bessie 要给他的雪牛来点细节。因此他给其中一个雪球加了个鼻子，来表示这是他那抽象的牛的头，并且把它称作雪球 $1$。

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

#### INPUT FORMAT (file snowcow.in):

• 1 x c（修改）：表示 Bessie 把一桶装有颜色 $c$ 的颜料泼到雪球 $x$ ，使得其子树上所有雪球被染色。
• 2 x（询问）：询问雪球 $x$ 的子树的颜色丰富度之和。 The first line contains $N,$ and the number of queries $Q$ ($1\le Q\le 10^5$).

The next $N-1$ lines each contain two space-separated integers $a$ and $b,$ describing a branch connecting snowballs $a$ and $b$ ($1 \le a, b \le N$).

Finally, the last $Q$ lines each contain a query. A query of the form

1 x c

indicates that Bessie splashed a bucket of juice of color $c$ on snowball $x,$ coloring all snowballs in the subtree of $x$. A line of the form

2 x

is a query for the sum of the colorfulness values of all snowballs in the subtree of $x$. Of course, $1\le x\le N$ and $1\le c\le 10^5.$

#### OUTPUT FORMAT (file snowcow.out):

For each query of type 2, print the sum of colorfulness values within the corresponding subtree.

Note that you should use 64-bit integers to avoid overflow.

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
After the first query of type 1, snowball 4 is dyed with color 1.

After the second query of type 1, snowballs 4 and 5 are dyed with color 1.

After the third query of type 1, all snowballs are dyed with color 1.

Problem credits: Michael Cao and Benjamin Qi

###### 提示
• Test cases 2-3 satisfy $N\le 10^2, Q\le 2\cdot 10^2.$
• Test cases 4-6 satisfy $N\le 10^3, Q\le 2\cdot 10^3.$
• 对于测试点 $2,3$，$1\le N\le 10^2,\$ $1\le Q\le 2\times 10^2$

对于测试点 $4\sim 6$，$\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$

#### 样例解释

执行完第一个修改后雪球 $4$ 被染上了颜色 $1$。

执行完第二个修改后雪球 $4$ 和雪球 $5$ 被染上了颜色 $2$。

执行完第三个修改后所有雪球都被染上了颜色 $1$。