P5443 [APIO2019] 桥梁

圣彼得堡市内所有水路长度总和约 $282$ 千米，市内水域面积占城市面积的 $7\%$。——来自维基百科

圣彼得堡位于由 $m$ 座桥梁连接而成的 $n$ 个岛屿上。岛屿用 $1$ 到 $n$ 的整数编号，桥梁用 $1$ 到 $m$ 的整数编号。每座桥连接两个不同的岛屿。有些桥梁是在彼得大帝时代建造的，其中一些是近期建造的。这导致了不同的桥梁可能有不同的重量限制。更具体地，只有重量不超过 $d_i$ 的汽车才能通过第 $i$ 座桥梁。有时圣彼得堡的一些桥梁会进行翻新，但这并不一定会使桥梁承重变得更好，也就是说，进行翻新的桥梁的 $d_i$ 可能会增加或减少。你准备开发一个产品，用于帮助公民和城市客人。目前，你开发的模块要能执行两种类型的操作： 1. 将桥梁 $b_j$ 的重量限制改为 $r_j$。 2. 统计一辆重为 $w_j$ 的汽车从岛屿 $s_j$ 出发能够到达多少个不同的岛屿。 请你回答所有第二种操作的答案。

无

无

对于全部数据，$1 \leq n \leq 5\times 10^4$，$0 \leq m \leq 10^5$，$1 \leq q \leq 10^5$。保证 $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$，$t_j \in {1,2}$。 详细子任务附加限制与分值如下表 **（注：这里给出的子任务与本题在这里的最终评测无关，仅供参考）** | 子任务 | 附加限制 | 分值 | | :----------: | :----------: | :----------: | | 1 | $n$, $m\leq 10^3$，$q\leq 10^4$ | 13 | | 2 | 岛屿和桥梁将形成一个树结构；$m=n-1$，$u_i=i$，$v_i=i+1$；（$1\leq i\leq m$） | 16 | | 3 | 岛屿和桥梁将形成一个完全二叉树结构；$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 | 所有 $t_i$ 均为 $2$ | 14 | | 5 | 岛屿和桥梁将形成一个树结构 | 13 | | 6 | 无特殊限制 | 27 |