← 返回题目列表

AtCoder · ttpc2019_h

H. 救济

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

配点 : 100 点

問題文

在这个世界上 有 N 个国家存在,这些国家有 1, 2, 3, \ldots, N 。 N 个国家到目前为止完全没有互相合作过,但由于各国之间的差距越来越大,寻求援助的国家也在增加,因此决定建立外交关系并互相提供援助。

各国的当前状况用两个整数表示。 X_i, P_i 什么时候可以工作X_i 是国家 i 的最大援助授受量,P_i 是根据援助量可以获救的国民人数。

具体来说,
X_i \ge 0 国是可以向其他国家提供援助的国家,一年内最多可以提供总计 |X_i| 的援助。
X_i < 0 国是可以接受其他国家援助的国家,一年内最多可以接受总计 |X_i| 的援助。
另外,如果国家 i 从其他国家总共接受了 x \ (x \le |X_i|) 的援助,P_i \times x 名国民可以得到救助。

目前,各国之间都没有建立外交关系,并且计划在接下来的 Q 年内建立外交关系。 该计划是每年建立一个外交关系,j 第 n 年的年初,国 a_j 和国家 连接 b_j 将建立外交关系。

这个 Q 按照年度计划顺序建立外交关系时,j 第 n 年能够通过支援救助的最大人数为每个 j ,请求解。 在

但某国可以提供支援的国家是,直接建立外交关系的国家,或通过多个外交关系间接连接的国家。

制約

  • 所有输入均为整数
  • 2 \le N \le 10^5
  • 1 \le Q \le \min(10^5, N(N-1)/2)
  • 0 \le |X_i| \le 10^9
  • \sum |X_i| \le 10^9
  • 1 \le P_i \le 10^9 \ (X_i < 0)
  • P_i = 0 \ (X_i \ge 0)
  • 1 \le a_i, b_i \le N
  • a_i \ne b_i
  • i \ne j 什么时候 (a_i, b_i) \ne (a_j, b_j)

入力

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

N
X_1 P_1
X_2 P_2
\vdots
X_N P_N
Q
a_1 b_1
a_2 b_2
\vdots
a_Q b_Q

出力

Q 行。 i 在每一行中,如果外交关系按计划建立, i 输出第 n 年能够被救助的最大人数。


入力例 1

3
2 0
3 0
-4 2
2
1 3
1 2

出力例 1

4
8
  • 第一年的话,从国家 1 向国家 3 提供一定量的支援, 2 可以救助4 人。
  • 在第 2 年,从国家 1 向国家 3 提供数量 1 的支援,以及从国家 2 通过国家 1 向国家 3 提供数量 3 的支援后,总计 8 人。

入力例 2

4
-5 1
-3 3
1 0
6 0
5
1 4
1 2
2 4
2 3
3 4

出力例 2

5
12
12
13
13

入力例 3

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

出力例 3

0
0
0
  • 没有能够提供支援的国家存在,因此无论建立多少外交关系,可以拯救的人数也只是 0 人。