{"raw_statement":[{"iden":"background","content":"**题目译自 [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/)。**"},{"iden":"statement","content":"Bajtazar 在一家货运公司工作，他目前的工作是将建筑材料从 Bajtocji 的首都运输到附近城镇的商店。在 Bajtocji，有 $n$ 座城市（编号从 $1$ 到 $n$），这些城市通过 $n-1$ 条道路相互连接。每条道路上都有一个加油站。\n\nBajtazar 一天的工作是这样的：他从首都（编号为 $1$ 的城市）出发，沿着最短路径到达城市 $x$，再原路返回。\n\nBajtazara 的儿子 Bitek 非常喜欢加油站里卖的玩具狗。玩具狗一共有 $m$ 种（编号从 $1$ 到 $m$），但每个加油站只提供一种玩具狗，因此收集玩具狗并非一件轻松的事情。\n\n现在给出 Bajtazara 每天前往的目的地，他想要知道他的儿子这天能够获得多少种玩具狗。麻烦的是，每个加油站里售卖的玩具狗的种类会发生变化，你能帮助他解决这个难题吗？\n"},{"iden":"input","content":"输入第一行三个整数 $n,m,z$，分别代表 Bajtocji 的城市数，玩具狗的种类数，查询的次数。\n\n接下来 $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$）。\n\n接下来 $z$ 行，每行描述一个询问或修改操作，格式如下：\n\n- 询问操作：$\\texttt{Z}\\ x$ 表示 Bajtazara 想要知道，从首都出发到城市 $x$（$2 \\leq x \\leq n$），能收集到多少种玩具狗。\n- 修改操作：$\\texttt{B}\\ i\\ c$ 表示将第 $i$ 条道路上加油站售卖的玩具狗的类型改为 $c$（$1 \\leq c \\leq m$，注意如果该加油站本来就售卖 $c$ 类型玩具狗，执行该操作后将不会有任何影响）。"},{"iden":"output","content":"对于每个 $\\texttt{Z}$ 操作，输出一行一个整数，代表这一天 Bajtazara 的儿子能获得的玩具狗的种类数。"},{"iden":"note","content":"【样例解释1】：\n\n![pp5XLWV.png](https://s1.ax1x.com/2023/04/05/pp5XLWV.png)\n\n注意该样例中存在一次修改操作，使得第二条道路上的加油站售卖的玩具狗的种类从 $2$ 变成了 $1$。\n\n【数据范围】：\n\n所有测试点均满足：$2 \\leq n \\leq 10^5$，$1 \\leq m,z \\leq 1.5 \\times 10^5$，且至少存在一个 $\\texttt{Z}$ 操作。\n\n| 子任务编号 | 约束| 分值|\n|:-:|:-:| :-: |\n| $1$| $n,m,z \\leq 100$| $7$  |\n| $2$| $n,z \\leq 2 \\times 10^3$| $9$  |\n|$3$ | 只有 $\\texttt{Z}$ 类型操作| $9 $  |\n| $4$| $m \\leq 15$|$15$|\n|$5$|道路 $i$ 连接城市 $i$ 和城市 $i+1$| $11$ |\n| $6$ | 刚开始时，每个加油站售卖的玩具狗类型都是 $1$，在后续的 $\\texttt{B}$ 类型操作中，玩具狗的类型会被更改为除 $1$ 之外的任意类型 | $13$ |\n| $7$| 无附加约束| $36$ |"}],"translated_statement":null,"sample_group":[["6 3 5\n1 2 3\n1 3 2\n3 4 3\n5 3 1\n6 4 2\nZ 5\nZ 6\nB 2 1\nZ 5\nZ 6","2\n2\n1\n3"],["8 4 20\n1 2 3\n8 2 4\n6 4 2\n1 6 1\n3 4 3\n4 5 2\n7 4 1\nZ 2\nZ 3\nZ 4\nZ 5\nZ 6\nZ 7\nZ 8\nB 4 4\nB 3 3\nB 7 4\nB 2 3\nZ 2\nZ 3\nZ 4\nZ 5\nZ 6\nZ 7\nZ 8\nB 3 4\nZ 7","1\n3\n2\n2\n1\n2\n2\n1\n2\n2\n3\n1\n2\n1\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}