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