Background

This problem is translated from XXVIII Olimpiada Informatyczna – Stage I Gang Biciaków.

Problem Description

Bajtazar works at a freight company. His current job is to transport construction materials from the capital of Bajtocja to shops in nearby towns. In Bajtocja, there are $n$ cities (numbered from $1$ to $n$), connected by $n - 1$ roads. Each road has a gas station.

Bajtazar’s workday is as follows: he leaves the capital (city $1$), travels along the shortest path to city $x$, and then returns along the same route.

Bajtazar’s son, Bitek, really likes the toy dogs sold at gas stations. There are $m$ types of toy dogs (numbered from $1$ to $m$), but each gas station sells only one type, so collecting them is not easy.

You are given Bajtazar’s destination each day. He wants to know how many different types of toy dogs his son can get that day. The trouble is that the type of toy dog sold at each gas station can change. Can you help him solve this problem?

Input Format

The first line contains three integers $n, m, z$, representing the number of cities in Bajtocja, the number of toy dog types, and the number of queries.

The next $n - 1$ lines describe the roads. The $i$-th line contains three integers $a_i, b_i, c_i$, meaning that the $i$-th road connects cities $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$), and the gas station on this road sells toy dog type $c_i$ ($1 \leq c_i \leq m$).

The next $z$ lines each describe a query or an update operation, in one of the following formats:

• Query operation: $\texttt{Z}\ x$ means Bajtazar wants to know, starting from the capital and going to city $x$ ($2 \leq x \leq n$), how many different types of toy dogs can be collected.
• Update operation: $\texttt{B}\ i\ c$ means changing the toy dog type sold at the gas station on the $i$-th road to $c$ ($1 \leq c \leq m$). Note that if the gas station already sells type $c$, then this operation has no effect.

Output Format

For each $\texttt{Z}$ operation, output one integer per line: the number of toy dog types that Bajtazar’s son can obtain that day.

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

Hint

[Sample Explanation 1]:

Note that in this sample there is one update operation, which changes the toy dog type sold at the gas station on the second road from $2$ to $1$.

[Constraints]:

All testdata satisfy: $2 \leq n \leq 10^5$, $1 \leq m, z \leq 1.5 \times 10^5$, and there is at least one $\texttt{Z}$ operation.

Translated by ChatGPT 5