← 返回题目列表

AtCoder · cpsco2019_s2_g

G. MST扩展

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

配点 : 500 点

問題文

N 頂点 M 给出了一个简单的无向连通边图。 i 第一条边是顶点 u_i 和 v_i 已连接,重量为 w_i 。 w_i是正整数常量或变量 x 。下面 处理所有 Q 查询。 在第

  • i 次查询中,一个正整数 求当 a_i 给出。
  • x=a_i 时最小生成树的权值。 当

制約

  • 2 \le N \le 5 \times 10^4
  • N-1 \le M \le min(5 \times 10^4, N(N-1)/2)
  • 1 \le u_i,v_i \le N
  • u_i \neq v_i
  • i \neq j 什么时候 (u_i,v_i) \neq (u_j,v_j) 和 (u_i,v_i) \neq (v_j,u_j)
  • 给定的图形已连接。 当
  • w_i 为常数时,1 \le w_i \le 10^9
  • 1 \le Q \le 5 \times 10^4
  • 1 \le a_i \le 10^9
  • 输入是一个字符 除 x 外均为整数。

入力

输入将以以下格式从标准输入给出。

但是, c_i 是一个字符 0 或 1 ,即 w_i 表示是常量还是变量。 当 c_i 是 当 0 时, w_i 是正整数常数, 输出 c_i 是 当 1 时, w_i 是一个字符 x 。

N M
u_1 v_1 c_1 w_1
u_2 v_2 c_2 w_2
:
u_M v_M c_M w_M
Q
a_1
a_2
 : 
a_Q

出力

Q 行。 打印第 i 行中, i 个查询的答案。


入力例 1

3 3
1 2 0 1
2 3 0 5
3 1 1 x
3
4
5
6

出力例 1

5
6
6

在这种情况下, 当

  • x \le 5 时,最小生成树的权值为 x+1
  • x \ge 5 时,最小生成树的权值为 6

。


入力例 2

9 15
1 3 0 954291757
2 3 1 x
2 4 1 x
1 5 0 138996221
2 5 0 353195922
3 5 1 x
4 5 0 913575467
1 6 0 824284691
1 7 1 x
2 7 1 x
1 8 0 131381221
6 8 0 208032501
7 8 0 973708325
5 9 1 x
6 9 0 298309896
5
215208399
554374432
47628333
810900084
87027328

出力例 2

1554451938
2793039057
625183720
3562616013
861577690