#P9295. [POI2020] Gang Biciaków

[POI2020] Gang Biciaków

题目背景

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

题目描述

Bajtazar 在一家货运公司工作,他目前的工作是将建筑材料从 Bajtocji 的首都运输到附近城镇的商店。在 Bajtocji,有 nn 座城市(编号从 11nn),这些城市通过 n1n-1 条道路相互连接。每条道路上都有一个加油站。

Bajtazar 一天的工作是这样的:他从首都(编号为 11 的城市)出发,沿着最短路径到达城市 xx,再原路返回。

Bajtazara 的儿子 Bitek 非常喜欢加油站里卖的玩具狗。玩具狗一共有 mm 种(编号从 11mm),但每个加油站只提供一种玩具狗,因此收集玩具狗并非一件轻松的事情。

现在给出 Bajtazara 每天前往的目的地,他想要知道他的儿子这天能够获得多少种玩具狗。麻烦的是,每个加油站里售卖的玩具狗的种类会发生变化,你能帮助他解决这个难题吗?

输入格式

输入第一行三个整数 n,m,zn,m,z,分别代表 Bajtocji 的城市数,玩具狗的种类数,查询的次数。

接下来 n1n-1 行,第 ii 行三个整数 ai,bi,cia_i,b_i,c_i,代表第 ii 条道路连接城市 aia_i 和城市 bib_i1ai,bin1 \leq a_i,b_i \leq n),该道路上的加油站售卖的玩具狗种类为 cic_i1cim1 \leq c_i \leq m)。

接下来 zz 行,每行描述一个询问或修改操作,格式如下:

  • 询问操作:Z x\texttt{Z}\ x 表示 Bajtazara 想要知道,从首都出发到城市 xx2xn2 \leq x \leq n),能收集到多少种玩具狗。
  • 修改操作:B i c\texttt{B}\ i\ c 表示将第 ii 条道路上加油站售卖的玩具狗的类型改为 cc1cm1 \leq c \leq m,注意如果该加油站本来就售卖 cc 类型玩具狗,执行该操作后将不会有任何影响)。

输出格式

对于每个 Z\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

提示

【样例解释1】:

pp5XLWV.png

注意该样例中存在一次修改操作,使得第二条道路上的加油站售卖的玩具狗的种类从 22 变成了 11

【数据范围】:

所有测试点均满足:2n1052 \leq n \leq 10^51m,z1.5×1051 \leq m,z \leq 1.5 \times 10^5,且至少存在一个 Z\texttt{Z} 操作。

子任务编号 约束 分值
11 n,m,z100n,m,z \leq 100 77
22 n,z2×103n,z \leq 2 \times 10^3 99
33 只有 Z\texttt{Z} 类型操作 99
44 m15m \leq 15 1515
55 道路 ii 连接城市 ii 和城市 i+1i+1 1111
66 刚开始时,每个加油站售卖的玩具狗类型都是 11,在后续的 B\texttt{B} 类型操作中,玩具狗的类型会被更改为除 11 之外的任意类型 1313
77 无附加约束 3636