G - MSTX Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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