P14623 [2018 KAIST RUN Fall] Coloring Roads

在 RUN 国，有 $n$ 个编号为 $1$ 到 $n$ 的城市。一些城市对之间由双向道路连接。恰好总共有 $n-1$ 条道路，并且对于任意两个城市，都存在唯一的路径连接它们。 编号为 $1$ 的城市是首都。最初所有道路都没有颜色。RUN 国的国王 Alex 要求你执行以下查询 $Q$ 次。 - $\tt{u\ c\ m}$：给定一个城市 $u$，一种颜色 $c$，和一个整数 $m$，将从 $u$ 到首都的唯一路径上的所有道路涂成颜色 $c$。即使道路已经有颜色，也要将其颜色改为 $c$。染色后，计算恰好有 $m$ 条道路被染色的颜色数量。 给定总共 $Q$ 次查询，计算每次查询第二部分的答案。

输入的第一行包含三个整数 $n, C, Q$（$1 \leq n, C, Q \leq 2 \times 10^5$），以单个空格分隔，分别表示 RUN 国的城市数量、可能的颜色数量和查询数量。接下来的 $n-1$ 行每行包含两个整数 $u, v$（$1 \leq u, v \leq n$），表示存在一条直接连接编号为 $u$ 和 $v$ 的城市之间的双向道路。 接下来的 $Q$ 行每行包含一个查询，包含 $3$ 个整数 $u, c, m$，如题目描述所述（$1 \leq u \leq n$，$1 \leq c \leq C$，$0 \leq m \leq n-1$）。

输出 $Q$ 行，每行对应一个查询。每行必须包含一个整数，即对应查询的答案。

最后一个查询的答案是 $1$，因为颜色 $5$ 被用于 $0$ 条道路。 --- 翻译由 DeepSeek V3 完成