P9295 [POI 2020/2021 R1] Gang Biciaków / 布茨帮

**题目译自 [XXVIII Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi28-1/dashboard/) [Gang Biciaków](https://sio2.mimuw.edu.pl/c/oi28-1/p/gan/)。**

Bajtazar 在一家货运公司工作，他目前的工作是将建筑材料从 Bajtocji 的首都运输到附近城镇的商店。在 Bajtocji，有 $n$ 座城市（编号从 $1$ 到 $n$），这些城市通过 $n-1$ 条道路相互连接。每条道路上都有一个加油站。 Bajtazar 一天的工作是这样的：他从首都（编号为 $1$ 的城市）出发，沿着最短路径到达城市 $x$，再原路返回。 Bajtazara 的儿子 Bitek 非常喜欢加油站里卖的玩具狗。玩具狗一共有 $m$ 种（编号从 $1$ 到 $m$），但每个加油站只提供一种玩具狗，因此收集玩具狗并非一件轻松的事情。 现在给出 Bajtazara 每天前往的目的地，他想要知道他的儿子这天能够获得多少种玩具狗。麻烦的是，每个加油站里售卖的玩具狗的种类会发生变化，你能帮助他解决这个难题吗？

输入第一行三个整数 $n,m,z$，分别代表 Bajtocji 的城市数，玩具狗的种类数，查询的次数。 接下来 $n-1$ 行，第 $i$ 行三个整数 $a_i,b_i,c_i$，代表第 $i$ 条道路连接城市 $a_i$ 和城市 $b_i$（$1 \leq a_i,b_i \leq n$），该道路上的加油站售卖的玩具狗种类为 $c_i$（$1 \leq c_i \leq m$）。 接下来 $z$ 行，每行描述一个询问或修改操作，格式如下： - 询问操作：$\texttt{Z}\ x$ 表示 Bajtazara 想要知道，从首都出发到城市 $x$（$2 \leq x \leq n$），能收集到多少种玩具狗。 - 修改操作：$\texttt{B}\ i\ c$ 表示将第 $i$ 条道路上加油站售卖的玩具狗的类型改为 $c$（$1 \leq c \leq m$，注意如果该加油站本来就售卖 $c$ 类型玩具狗，执行该操作后将不会有任何影响）。

对于每个 $\texttt{Z}$ 操作，输出一行一个整数，代表这一天 Bajtazara 的儿子能获得的玩具狗的种类数。

【样例解释1】：  注意该样例中存在一次修改操作，使得第二条道路上的加油站售卖的玩具狗的种类从 $2$ 变成了 $1$。 【数据范围】： 所有测试点均满足：$2 \leq n \leq 10^5$，$1 \leq m,z \leq 1.5 \times 10^5$，且至少存在一个 $\texttt{Z}$ 操作。 | 子任务编号 | 约束| 分值| |:-:|:-:| :-: | | $1$| $n,m,z \leq 100$| $7$ | | $2$| $n,z \leq 2 \times 10^3$| $9$ | |$3$ | 只有 $\texttt{Z}$ 类型操作| $9 $ | | $4$| $m \leq 15$|$15$| |$5$|道路 $i$ 连接城市 $i$ 和城市 $i+1$| $11$ | | $6$ | 刚开始时，每个加油站售卖的玩具狗类型都是 $1$，在后续的 $\texttt{B}$ 类型操作中，玩具狗的类型会被更改为除 $1$ 之外的任意类型 | $13$ | | $7$| 无附加约束| $36$ |