「POI 2020/2021 R1」Gang Biciaków

题目描述

Bajtazar 在一家货运公司工作，负责将建筑材料从 Bajtocji 的首都（编号为 $1$ 的城市）运输到附近城镇的商店。Bajtocji 有 $n$ 座城市（编号从 $1$ 到 $n$），通过 $n-1$ 条道路相互连接。每条道路上都有一个加油站。

Bajtazar 每天的工作流程：从首都出发，沿着最短路径到达城市 $x$，然后原路返回。

Bajtazar 的儿子 Bitek 非常喜欢加油站出售的玩具狗。玩具狗共有 $m$ 种（编号从 $1$ 到 $m$），每个加油站只提供一种玩具狗。

给定 Bajtazar 每天前往的目的地，需要计算他的儿子当天能够获得多少种不同的玩具狗。困难在于，每个加油站售卖的玩具狗种类可能会发生变化。

输入格式

第一行包含三个整数 $n, m, z$，分别表示城市数量、玩具狗种类数量和操作次数。

接下来 $n-1$ 行，每行包含三个整数 $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$ 行，每行描述一个操作：

• 查询操作：Z x - 查询从首都到城市 $x$（$2 \leq x \leq n$）的路径上能收集到多少种不同的玩具狗
• 修改操作：B i c - 将第 $i$ 条道路上的加油站售卖的玩具狗种类改为 $c$（$1 \leq c \leq m$）

输出格式

对于每个 Z 操作，输出一行一个整数，表示当天能获得的玩具狗种类数。

样例 1

输入

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

解释：样例中存在一次修改操作，将第二条道路上的加油站售卖的玩具狗种类从 $2$ 改为 $1$。

样例 2

输入

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 和 gan2.out。

该样例满足：

• $n = 2^{16} - 1$
• $m = 100$
• $z = 10^5$
• 整棵树形成了一个满二叉树结构
• 只有 Z 类型操作

样例 4

见附加文件下的 gan3.in 和 gan3.out。

该样例满足：

• $n = 10^5$
• $m = 15$
• $z = 1.5 \times 10^5$
• 对于所有 $j \in [1, 5 \times 10^4)$，都存在一条连接城市 $j$ 和城市 $j+1$ 的道路
• 对于所有 $j \in (5 \times 10^4, 10^5]$，都存在一条连接城市 $5 \times 10^4$ 和城市 $j$ 的道路

样例 5

见附加文件下的 gan4.in 和 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$
• 至少存在一个 Z 操作

子任务

子任务编号	约束	分值
1	$n, m, z \leq 100$	7
2	$n, z \leq 2 \times 10^3$	9
3	只有 Z 类型操作
4	$m \leq 15$	15
5	道路 $i$ 连接城市 $i$ 和城市 $i+1$	11
6	初始时所有加油站类型为 $1$，后续修改为除 $1$ 外的类型	13
7	无附加约束	36