P5443 [APIO2019] Bridges

The total length of all waterways in Saint Petersburg is about $282$ km, and the water area accounts for $7\%$ of the city area. — From Wikipedia.

Saint Petersburg is located on $n$ islands connected by $m$ bridges. The islands are numbered with integers from $1$ to $n$, and the bridges are numbered with integers from $1$ to $m$. Each bridge connects two different islands. Some bridges were built in the era of Peter the Great, while others were built more recently. As a result, different bridges may have different weight limits. More specifically, only cars with weight not exceeding $d_i$ can cross bridge $i$. Sometimes, some bridges in Saint Petersburg are renovated, but this does not necessarily make their load capacity better; that is, after renovation, the $d_i$ of a bridge may increase or decrease. You are going to develop a product to help citizens and city visitors. Currently, the module you are developing needs to support two types of operations: 1. Change the weight limit of bridge $b_j$ to $r_j$. 2. Count how many different islands a car of weight $w_j$ can reach starting from island $s_j$. Please answer all queries of the second type.

The first line contains two integers $n$ and $m$, representing the number of islands and the number of bridges in Saint Petersburg. The next $m$ lines each contain three integers $u_i, v_i, d_i$. Line $i$ describes a bridge connecting islands $u_i$ and $v_i$, with an initial weight limit of $d_i$. The next line contains one integer $q$, representing the number of operations. The next $q$ lines describe the operations in order, one per line. The first integer on each line is $t_j$, indicating the operation type: - If $t_j = 1$, this is the first type of operation. The line then contains two integers $b_j$ and $r_j$, meaning the weight limit of bridge $b_j$ will become $r_j$. - If $t_j = 2$, this is the second type of operation. The line then contains two integers $s_j$ and $w_j$, meaning a car of weight $w_j$ will start from island $s_j$.

For each query of the second type, output one line with one integer representing the answer.

For all testdata, $1 \leq n \leq 5 \times 10^4$, $0 \leq m \leq 10^5$, $1 \leq q \leq 10^5$. It is guaranteed that $1 \leq u_i, v_i, s_j \leq n$, $u_i \neq v_i$, $1 \leq d_i, r_j, w_j \leq 10^9$, $1 \leq b_j \leq m$, and $t_j \in \{1, 2\}$. The detailed additional constraints and scores for the subtasks are shown in the table below. | Subtask | Additional Constraints | Score | | :----------: | :----------: | :----------: | | 1 | $n, m \leq 10^3$, $q \leq 10^4$ | 13 | | 2 | The islands and bridges form a tree; $m = n - 1$, $u_i = i$, $v_i = i + 1$ ($1 \leq i \leq m$) | 16 | | 3 | The islands and bridges form a complete binary tree; $n = 2^k - 1$, $m = n - 1$, $u_i = \frac{i+1}{2}$, $v_i = i + 1$ ($1 \leq k \leq 15$, $1 \leq i \leq m$) | 17 | | 4 | All $t_i$ are $2$ | 14 | | 5 | The islands and bridges form a tree | 13 | | 6 | No special constraints | 27 | Translated by ChatGPT 5