Bessie's Snow Cow

题目描述

冬天来到了农场，和每年冬天开始时一样，Bessie 正在堆一个雪牛！大多数时候，Bessie 会努力让她的雕塑尽可能像一头真正的奶牛。然而，今年她灵感迸发，决定走更抽象的路线，制作一个树形的雕塑：由 $N$ 个雪球 $(1\le N\le 10^5)$ 通过 $N-1$ 根树枝连接而成，每根树枝连接一对雪球，并且任意两颗雪球之间都有唯一的一条路径。

Bessie 在其中一个雪球上加了一个鼻子，使其代表这头抽象雪牛的头部，并将其指定为 1 号雪球。为了增加视觉效果，她计划以艺术的方式把一些雪球染成不同颜色：她把旧牛奶桶装满彩色染料并泼洒到雕塑上。颜色用 $1 \ldots 10^5$ 范围内的整数表示，并且 Bessie 拥有每一种颜色的染料桶的无限供应。

当 Bessie 用一桶染料泼洒一个雪球时，该雪球的整棵子树中的所有雪球也会被同样的颜色泼到（若雪球 $y$ 在雪球 $x$ 的子树中，表示在从 $y$ 到头部雪球的路径上包含 $x$）。通过小心地泼洒每种颜色，Bessie 确保一个雪球被泼到的所有颜色都会保持可见。例如，如果一个雪球已有颜色 $[1,2,3]$，Bessie 再用颜色 $4$ 泼它，那么该雪球将拥有颜色 $[1,2,3,4]$。

在进行了若干次泼洒之后，Bessie 还可能想知道雪牛的某一部分有多“多彩”。雪球 $x$ 的“多彩度”（colorfulness）等于不同颜色 $c$ 的数量，使得雪球 $x$ 被染成颜色 $c$。如果 Bessie 询问你关于雪球 $x$，你需要回答：雪球 $x$ 的子树中所有雪球的多彩度之和。

请帮助 Bessie 在某些时刻求出她的雪牛的多彩程度。

输入格式

第一行包含 $N$ 以及查询数量 $Q$（$1\le Q\le 10^5$）。 接下来的 $N-1$ 行每行包含两个用空格分隔的整数 $a$ 和 $b$，描述连接雪球 $a$ 与雪球 $b$ 的一根树枝（$1 \le a, b \le N$）。 最后的 $Q$ 行每行包含一个查询。形如 1 x c 的查询表示 Bessie 将颜色为 $c$ 的染料泼在雪球 $x$ 上，使雪球 $x$ 的子树中所有雪球都被染上颜色 $c$。形如 2 x 的查询表示询问雪球 $x$ 的子树内所有雪球的多彩度之和。当然，$1\le x\le N$ 且 $1\le c\le 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

提示

SCORING: $Q$ 的定义见下文。 测试点 2-3 满足 $N\le 10^2, Q\le 2\cdot 10^2.$ 测试点 4-6 满足 $N\le 10^3, Q\le 2\cdot 10^3.$ 第一次类型为 1 的查询后，雪球 4 被染上颜色 1。 第二次类型为 1 的查询后，雪球 4 和 5 被染上颜色 1。 第三次类型为 1 的查询后，所有雪球都被染上颜色 1。 题目鸣谢：Michael Cao 和 Benjamin Qi

标签: USACO|2019|Platinum

来源

USACO|2019|Platinum