← 返回题目列表

AtCoder · abc040_d

D. 道路老化对策

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

問題文

在某些国家/地区 有 N 个城市,每个城市都有 它们的编号最大为 1 从 N 。连接这些城市 M 有一条路,i 真正的道路是城市 a_i 和城市 它连接 b_i , 它建于y_i 。

这个国家的人民是非常焦虑的人,所以他们可能不会使用太旧的道路,因为他们认为发生事故的风险很高。因此您决定调查这个国家的交通状况。

Q 给出了国家信息。j 关于第一个公民、城市 我住在 v_j ,它的建造年份是 w_j 年以前 (w_j 我们知道您不会使用(包括确切的)道路。

对于每个公民,找出仅使用道路从该人居住的城市可以到达的城市数量。

制約

  • 1 ≦ N ≦ 100,000
  • 0 ≦ M ≦ 200,000
  • 1 ≦ a_i,b_i ≦ N
  • a_i ≠ b_i
  • 1 ≦ y_i ≦ 200,000
  • 1 ≦ Q ≦ 100,000
  • 1 ≦ v_j ≦ N
  • 0 ≦ w_j ≦ 200,000

部分点

  • 50 在点的测试用例中, 输出N ≦ 1,000, M ≦ 2,000, Q ≦ 1,000 。

入力

输入是按以下格式从标准输入给出的。

N M
a_1 b_1 y_1
:
a_M b_M y_M
Q
v_1 w_1
:
v_Q w_Q

出力

Q 行。其中 j 行中,j 输出该国公民仅使用道路即可前往的城市数量。


入力例1

5 4
1 2 2000
2 3 2004
3 4 1999
4 5 2001
3
1 2000
1 1999
3 1995

出力例1

1
3
5

Q 对于每个国家,答案如下。

  • 1 第一人称是城市 我住在 1 。 请勿使用2000 之前修建的道路。城市 通向 1 的唯一路径 2000 自当年建成以来,这座城市 除了 1 之外你不能去任何其他地方。因此答案是 我住在 1 。
  • 2 第一人称是城市 我住在 1 和城市 2 呀 您可以前往 3 。然而, 由于1999 之前修建的道路未使用,该市 4 。因此答案是 3 。
  • 3 第一个人是 1995 所有道路都比这新,因此您可以使用所有道路到达所有城市。因此答案是 5 。

入力例2

4 5
1 2 2005
3 1 2001
3 4 2002
1 4 2004
4 2 2003
5
1 2003
2 2003
1 2001
3 2003
4 2004

出力例2

3
3
4
1
1

入力例3

4 5
1 2 10
1 2 1000
2 3 10000
2 3 100000
3 1 200000
4
1 0
2 10000
3 100000
4 0

出力例3

3
3
2
1

连接相同两个城市的道路 2 请注意,可能不仅仅是书籍,而且某些城市可能无法通过所有道路到达。