题目描述

题目译自 XXVIII Olimpiada Informatyczna – I etap Gang Biciaków

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 的儿子能获得的玩具狗的种类数。

6 3 5
1 2 3
1 3 2
3 4 3
5 3 1
6 4 2
Z 5
Z 6
B 2 1
Z 5
Z 6

2
2
1
3

8 4 20
1 2 3
8 2 4
6 4 2
1 6 1
3 4 3
4 5 2
7 4 1
Z 2
Z 3
Z 4
Z 5
Z 6
Z 7
Z 8
B 4 4
B 3 3
B 7 4
B 2 3
Z 2
Z 3
Z 4
Z 5
Z 6
Z 7
Z 8
B 3 4
Z 7

1
3
2
2
1
2
2
1
2
2
3
1
2
1
1

样例 3

见附加文件下 [gan2.in](file:gan2.in) 和 [gan2.out](file:gan2.out)。

该样例满足 $n=2^{16}-1$，$m=100$，$z=10^5$，整棵树形成了一个满二叉树结构，且只有 $\texttt{Z}$ 类型操作。

样例 4

见附加文件下 [gan3.in](file:gan3.in) 和 [gan3.out](file:gan3.out)。

该样例满足 $n=10^5$，$m=15$，$z=1.5\times 10^5$，$\forall j \in [1,5 \times 10^4)$，都存在一条连接城市 $j$ 和城市 $j+1$ 的道路，$\forall j \in (5 \times 10^4,10^5]$，都存在一条连接城市 $5 \times 10^4$ 和城市 $j$ 的道路。

样例 5

见附加文件下 [gan4.in](file:gan4.in) 和 [gan4.out](file:gan4.out)。

该样例满足 $n=10^5$，$m=1.5 \times 10^5$，$z=1.5\times 10^5$，且道路 $i$ 连接了城市 $i$ 和城市 $i+1$。

数据范围与提示

所有测试点均满足：$2 \leq n \leq 10^5$，$1 \leq m,z \leq 1.5 \times 10^5$，且至少存在一个 $\texttt{Z}$ 操作。