11358: 洛谷P1710 - 地铁涨价
[Creator : ]
Description
博艾市除了有海底高铁连接中国大陆、台湾与日本,市区里也有很成熟的轨道交通系统。我们可以认为博艾地铁系统是一个无向连通图。博艾有 $N$ 个地铁站,同时有 $M$ 小段地铁连接两个不同的站。
地铁计价方式很简单。从 A 站到 B 站,每经过一小段铁路(连接直接相邻的两个点的一条边),就要收取 $1$ 博艾元。也就是说,从 A 站到 B 站,选择的路径不一样,要价也会不同。
我们认为凡华中学在 $1$ 号地铁站。学生们通过地铁通勤,他们当然知道选择最短路来坐车的话,票价最便宜。
然而博艾地铁公司经营不善,一直亏损,于是他们打算提价。提价一次就是将一小段铁路原来收费 $1$ 元改收 $2$ 元。同一小段的铁路不会多次提价。他们打算提价 $Q$ 次。
学生们知道,如果他们到学校的一条最短路径中的一小段提价了,可以改变路径,使总票价不变。然而随着一条一条的铁路被提价,当居住在某个站附近的学生发现,提价后,没有任何一种方案可以从家到学校的费用和初始费用相等时,就会不满。
现在地铁公司希望知道,对于每一次涨价,有多少个站,学生会因为涨价而不满呢?
地铁计价方式很简单。从 A 站到 B 站,每经过一小段铁路(连接直接相邻的两个点的一条边),就要收取 $1$ 博艾元。也就是说,从 A 站到 B 站,选择的路径不一样,要价也会不同。
我们认为凡华中学在 $1$ 号地铁站。学生们通过地铁通勤,他们当然知道选择最短路来坐车的话,票价最便宜。
然而博艾地铁公司经营不善,一直亏损,于是他们打算提价。提价一次就是将一小段铁路原来收费 $1$ 元改收 $2$ 元。同一小段的铁路不会多次提价。他们打算提价 $Q$ 次。
学生们知道,如果他们到学校的一条最短路径中的一小段提价了,可以改变路径,使总票价不变。然而随着一条一条的铁路被提价,当居住在某个站附近的学生发现,提价后,没有任何一种方案可以从家到学校的费用和初始费用相等时,就会不满。
现在地铁公司希望知道,对于每一次涨价,有多少个站,学生会因为涨价而不满呢?
Input
第一行为三个整数 $N,M,Q$。
接下来 $M$ 行,每行 $2$ 个整数 $a_i,b_i,$ 表示第 $i$ 条铁路连接的两个站。$i$ 表示铁路编号。
接下来 $Q$ 行,每行一行整数 $r_j$,表示每次涨价的铁路编号。
接下来 $M$ 行,每行 $2$ 个整数 $a_i,b_i,$ 表示第 $i$ 条铁路连接的两个站。$i$ 表示铁路编号。
接下来 $Q$ 行,每行一行整数 $r_j$,表示每次涨价的铁路编号。
Output
输出共 $Q$ 行。每行一个整数表示不满的车站数量。
Constraints
- 对于 $20\%$ 的数据 $N \le 100,Q \le 30$。
- 对于 $40\%$ 的数据 $Q \le 30$。
- 对于 $70\%$ 的数据正确的输出结果中,不会有超过 $50$ 种不一样的整数(数据范围剧透解法系列)
- 对于 $100\%$ 的数据 $N \le 100000,Q \le M \le 200000$。
- 对于 $40\%$ 的数据 $Q \le 30$。
- 对于 $70\%$ 的数据正确的输出结果中,不会有超过 $50$ 种不一样的整数(数据范围剧透解法系列)
- 对于 $100\%$ 的数据 $N \le 100000,Q \le M \le 200000$。
Sample 1 Input
5 6 5
1 2
1 3
4 2
3 2
2 5
5 3
5
2
4
1
3
Sample 1 Output
0
2
2
4
4
次数 车站2 车站3 车站4 车站5 初始 1 1 2 2 1 1 1 2 2 2 1 2 2 3 3 1 2 2 3 4 2 2 3 3 5 2 2 4 3