分数: 700 点
问题陈述
Takahashi 发现了一个无向连通图 N 顶点和 M 边缘。顶点已编号 1 通过 N。的 i第一条边连接顶点 a_i 和 b_i,重量为 c_i.
他会打 Q 使用此图表的游戏轮次。在 i第一轮,两个顶点 S_i 和 T_i 被指定,他将选择边的子集,使得可以从至少一个顶点到达任何顶点 S_i or T_i 通过遍历选定的边。
对于每一轮,找到 Takahashi 选择的边的最小可能总重量。
约束
- 1 ≦ N ≦ 4,000
- 1 ≦ M ≦ 400,000
- 1 ≦ Q ≦ 100,000
- 1 ≦ a_i,b_i,S_i,T_i ≦ N
- 1 ≦ c_i ≦ 10^{9}
- a_i \neq b_i
- S_i \neq T_i
- 给定的图形已连接。
部分分数
- 在测试集中值得 200 点, Q = 1.
- 在测试集中值得另一个 300 点, Q ≦ 3000.
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 c_1 a_2 b_2 c_2 : a_M b_M c_M Q S_1 T_1 S_2 T_2 : S_Q T_Q
输出
打印 Q 行。的 i第行应包含 Takahashi 选择的边的最小可能总权重。
示例输入 1
4 3 1 2 3 2 3 4 3 4 5 2 2 3 1 4
示例输出 1
8 7
我们将检查每一轮:
- 在 1-st 回合,选择边缘 1 和 3 达到最小总重量 8.
- 在 2- 第二轮,选择边缘 1 和 2 达到最小总重量 7.
示例输入 2
4 6 1 3 5 4 1 10 2 4 6 3 2 2 3 4 5 2 1 3 1 2 3
示例输出 2
8
此输入满足两个部分分数的附加约束。