AT_joi2019ho_e 珍しい都市 (Unique Cities)

JOI 国有 $N$ 个城市，编号为 $1$ 到 $N$。这些城市通过 $N-1$ 条道路相连。第 $i$ 条道路（$1 \leq i \leq N-1$）连接城市 $A_i$ 和城市 $B_i$，且道路是双向通行的。任意两个城市之间都可以通过若干条道路互相到达。 JOI 国有若干种特产，每种特产用 $1$ 到 $M$ 的编号表示（可能存在某些编号未被使用）。每个城市生产一种特产，城市 $j$（$1 \leq j \leq N$）生产编号为 $C_j$ 的特产。多个城市可能生产同一种特产。 两个城市之间的距离定义为它们之间需要经过的最少道路数。 对于城市 $x$（$1 \leq x \leq N$），如果城市 $y$（$1 \leq y \leq N,\, y \neq x$）满足对于所有其他城市 $z$（$1 \leq z \leq N,\, z \neq x,\, z \neq y$），城市 $x$ 到城市 $y$ 的距离与城市 $x$ 到城市 $z$ 的距离都不相同，则称城市 $y$ 对于城市 $x$ 来说是“珍稀城市”。 JOI 国的大臣 $K$ 想知道，对于每个城市 $j$（$1 \leq j \leq N$），从该城市出发，所有“珍稀城市”所生产的特产有多少种。 请你根据 JOI 国的道路信息和每个城市生产的特产编号，编写程序，计算每个城市从自身出发能看到的“珍稀城市”所生产的特产种类数。

输入从标准输入读入，格式如下： > $N$ $M$ > $A_1$ $B_1$ > $\vdots$ > $A_{N-1}$ $B_{N-1}$ > $C_1$ $\cdots$ $C_N$

输出共 $N$ 行。第 $j$ 行（$1 \leq j \leq N$）输出从城市 $j$ 出发能看到的“珍稀城市”所生产的特产种类数。

### 限制条件 - $2 \leq N \leq 200\,000$。 - $1 \leq M \leq N$。 - $1 \leq A_i \leq N$（$1 \leq i \leq N-1$），$1 \leq B_i \leq N$（$1 \leq i \leq N-1$）。 - 对于所有 $i$，$A_i$ 和 $B_i$ 均为有效城市编号。 - 任意两个城市之间都可以通过若干条道路互相到达。 - $1 \leq C_j \leq M$（$1 \leq j \leq N$）。 ### 子任务 1. （4 分）$N \leq 2\,000$。 2. （32 分）$M = 1$。 3. （32 分）$M = N$，且 $C_j = j$（$1 \leq j \leq N$）。 4. （32 分）无额外限制。 # 样例说明 1 对于城市 $1$，珍稀城市为城市 $2, 3$，它们生产的特产分别为 $2, 1$，所以答案为 $2$ 种。 对于城市 $2$，没有珍稀城市，所以答案为 $0$ 种。 对于城市 $3$，珍稀城市为城市 $1$，它生产的特产为 $1$，所以答案为 $1$ 种。 对于城市 $4$，珍稀城市为城市 $1, 3$，它们都生产特产 $1$，所以答案为 $1$ 种。 对于城市 $5$，珍稀城市为城市 $1, 3$，它们都生产特产 $1$，所以答案为 $1$ 种。 注意，编号为 $3$ 的特产不存在。 # 样例说明 2 该输入满足子任务 $2$ 的限制条件。 # 样例说明 3 该输入满足子任务 $3$ 的限制条件。 由 ChatGPT 4.1 翻译