← 返回题目列表

AtCoder · joi2016ho_c

C. 火车票价

中文机器翻译题面 查看原题

配点: 100 点

在JOI国家 有 N 个城市,每个城市都有 它的编号为 1, 2, \ldots, N 。城市 1 是JOI国的首都。

另外,JOI国家只有一家铁路公司,而这家公司是 它运营 M 路线。这些路线中的每一条 它的编号为 1, 2, \ldots, M 并且i 番目 (1 \leqq i \leqq M) 路线为城市路线 U_i 和城市 它连接 V_i 双向连接。除铁路外,无法在城市之间旅行。此外,现在可以通过连接多条路线从任何城市前往任何其他城市。

目前,所有航线的票价均为 1 这是一个圆圈。陷入财务困境的铁路公司将 Q 我们已计划在年内提高多条航线的票价。在这个计划中,从计划一开始, j 年目 (1 \leqq j \leqq Q) 年初航线 R_j 票价 1 从日元 2 我们计划将价格提高到日元。已上涨航线的票价将长期保持不变。 2 价格维持日元不变,不会再次上调。

顺便说一下,这个铁路公司每年都会对各个城市的居民进行满意度调查。项目开始前,各城市居民对铁路公司表示满意,但有可能部分居民对涨价感到不满。

每年的满意度调查是在当年涨价实施后进行的。因此,j 年目 (1 \leqq j \leqq Q)满意度调查 R_1, R_2, \ldots, R_j 票价上涨已完成,其他航线票价维持不变。j 年目 (1 \leqq j \leqq Q)满意度调查发现 当且仅当满足以下条件时, k (2 \leqq k \leqq N)的居民才会对铁路公司不满意:

  • 城市当前票价 k 的首都城市 前往 1 的最低费用为 k 来自城市 这个想法是建立一条通往 1 的最低成本。

但是,当使用多条路线旅行时,费用为每条路线的票价总和。还有,这座城市 1 的居民对铁路公司没有任何投诉。请注意,涨价后票价达到最低成本的路线可能与计划开始前票价达到最低成本的路线不同。

在实施该计划之前, Q 在每年的居民满意度调查中,我们都会计算出居民对铁路公司不满意的城市数量。

課題

JOI 给定一个国家的铁路线信息和提高票价的计划,编写一个程序,找出每次满意度调查中居民对铁路公司不满意的城市数量。


入力

从标准输入读取以下输入。

  • 1 行中, 请输出第3 整数 给出了 N, M, Q 以空格作为分隔符。这些适用于 JOI 国家。 N 城市和 M 条航线,有计划涨价。 Q 代表年份。
  • 继续 M 行 i 行目 (1 \leqq i \leqq M)有2 整数 给出了 U_i, V_i 以空格作为分隔符。这些是i 第条路线是城市 这表明 U_i 和城市 它连接 V_i 已连接。
  • 继续 Q 行 j 行目 (1 \leqq j \leqq Q)中,整数 R_j 。这是计划 j 年份路线 这表明 R_j 的票价将会上涨。

出力

到标准输出 输出 Q 请按行输出。j 行目 (1 \leqq j \leqq Q)有j 输出年度满意度调查中居民不满意的城市数量。


制限

所有的输入数据满足以下条件。

  • 2 \leqq N \leqq 100\,000.
  • 1 \leqq Q \leqq M \leqq 200\,000.
  • 1 \leqq U_i \leqq N (1 \leqq i \leqq M).
  • 1 \leqq V_i \leqq N (1 \leqq i \leqq M).
  • U_i \neq V_i (1 \leqq i \leqq M).
  • 1 \leqq R_j \leqq M (1 \leqq j \leqq Q).
  • R_j \neq R_k (1 \leqq j < k \leqq Q).
  • 哪个 2 即使对于两个城市,也没有直接连接它们的路线。 1 或更少。
  • 对于任何城市,从一个城市到另一个城市 您可以选择多条路线前往 1 。

小課題

小課題 1 [12 点]

满足以下条件。

  • N \leqq 100.
  • M \leqq 4\,950.
  • Q \leqq 30.

小課題 2 [14 点]

  • Q \leqq 30 很满意。

小課題 3 [35 点]

  • 正确输出中出现的整数是 它小于或等于 50 类型。

小課題 4 [39 点]

没有其他限制。


入力例 1

5 6 5
1 2
1 3
4 2
3 2
2 5
5 3
5
2
4
1
3

出力例 1

0
2
2
4
4

在此输入示例中,每个城市是 前往 1 的票价如下表所示。

例如, 当分解为3 2018年满意度调查中,我市 3 和城市 它连接 5 的居民不满意,所以输出 输出 3 在线 2 。 你只需要砍掉


入力例 2

4 6 6
1 2
1 3
1 4
2 3
2 4
3 4
1
4
2
5
3
6

出力例 2

1
1
2
2
3
3

入力例 3

2 1 1
1 2
1

出力例 3

1