#2085. 「APIO2019」桥梁

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: StudyingFather

题目描述

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

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

  1. 将桥梁 b_j 的重量限制改为 r_j
  2. 统计一辆重为 w_j 的汽车从岛屿 s_j 出发能够到达多少个不同的岛屿。

请你回答所有第二种操作的答案。

输入格式

第一行包含两个整数 n m ——表示圣彼得堡的岛屿数量与桥梁数量。

接下来 m 行,每行三个整数 u_i, v_i, d_i 。第 i 行的整数描述了一座连接岛屿 u_i v_i ,初始时重量限制为 d_i 的桥梁。

接下来一行一个整数 q ——表示操作的数量。

接下来 q 行按顺序每行描述一个操作。

每行第一个整数 t_j 表示操作类型:

  • t_j = 1 ,则该操作是第一种类型,该行接下来给定两个整数 b_j r_j ,表示桥梁 b_j 的重量限制将变为 r_j
  • t_j = 2 ,则该操作是第二种类型,该行接下来给定两个整数 s_j w_j ,表示一辆重为 w_j 的汽车将要从第 s_j 个岛屿出发。

输出格式

对于每个第二种类型的询问,输出一行一个整数表示答案。

样例

样例输入 1

3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2

样例输出 1

3
2
3

样例说明 1

绿线表示当前询问的汽车可以通过的桥梁。绿色顶点代表这辆车可以到达的岛屿。箭头指向汽车最初所在的岛屿。

bridge1.png

样例输入 2

7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3

样例输出 2

1
7
7
5
7
7
4

样例说明 2

bridge2.png

数据范围与提示

对于全部数据, 1\le n\le 5\times 10^4,0\le m\le 10^5,1\le q\le 10^5 。保证 1\le u_i,v_i,s_j\le n,u_i\not =v_i,1\le d_i,r_j,w_j\le 10^9,1\le b_j\le m,t_j\in\{1,2\}

详细子任务附加限制与分值如下表。

子任务 附加限制 分值
1 n,m\le 10^3,q\le 10^4 13
2 岛屿和桥梁将形成一个树结构, m = n - 1, u_i = i, v_i = i + 1\ (1 \le i \le m) 16
3 岛屿和桥梁将形成一个完全二叉树结构, n = 2^k - 1, m = n - 1, u_i =\lfloor \frac{i+1} {2} \rfloor, v_i = i + 1\ (1 \le k \le 15,1 \le i \le m) 17
4 所有 t_j 均为 2 14
5 岛屿和桥梁将形成一个树结构, m = n - 1 13
6 无特殊限制 27