← 返回题目列表

AtCoder · utpc2020_i

I. UTPC王国

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

問題文

在UTPC王国 N 镇 1, \ldots, N 和 M 有一条书路,i 第一条路是一座城市 A_i 和城市 B_i 已连接。 以城镇为顶点、以道路为边的图是无向连通图,虽然可能包含多条边,但不具有自环。

道路上会出现危险的怪物。i 道路的危险度是根据出现的怪物的强度决定的整数。 C_i 。然而,C_1, \ldots, C_M 是不同的。

旅​​程是从某个城市出发并沿着多条道路前往该城市的一系列道路。旅程 J = (J_1, J_2, \ldots, J_L) 的危险级别是 在 \sum_{i = 1}^{L} (10^6)^{C_{J_i}} 中定义。 还有,这座城市 i 和城市 j 关系不好,2 由连接两个城市的旅程的最低风险级别定义。当这样的旅程不存在时,关系就会不好 10^{10^{10}} 。

UTPC王国是一个非常不幸的王国。i 这一年, 由于灾难,T_i 道路无法通行。 由于道路无法通行,镇上各族人的敌意日益加深,互相打斗,局势十分危险。 如果有道路直接连接这些城市群,我们决定同时关闭它们,使它们无法通行,以维护国家的和平。此外,如果因该措施的影响而在城镇中出现相互不和的群体,则将重复类似的措施。 该操作显示持续有限次数。道路一旦无法通行,就永远无法再通行。

Q 提供了年内因灾害而无法通行的道路信息。

i 年内首次因封闭或灾害而无法通行的道路数量总和。 请输出 S_i 。 然而,T_i 已加密,无法直接读取。 X_i 作为输入给出,S_{i-1} \oplus X_i = T_i 作为T_i 已恢复。 (\oplus 代表异或, 假设它是S_0 是 由于它被视为 0 。 )

另请注意,因灾难而无法通行的道路可能已经关闭。

制約

  • 输入全部为整数。
  • 1 \le N, M, Q \le 3 \times 10^5
  • 1 \le A_i, B_i \le N
  • 1 \le C_i \le 10 ^ 9
  • C_i 是不同的。
  • 1 \le T_i = S_{i-1} \oplus X_{i} \le M
  • T_i 是不同的。
  • 以城镇为顶点、高速公路为边的图是无向连通图,虽然可能包含多条边,但不包含自环。

入力

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

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M
Q
X_1
\vdots
X_Q

出力

Q 行。i 行中,i 年内首次因封闭或灾害而无法通行的道路数量总和。 请输出 S_i 。


入力例1

3 4
1 2 1
2 3 2
3 1 3
1 2 4
2
1
10

出力例1

8
2

1 今年 S_0 \oplus 1 = 1 所以 由于灾难, 1 道路无法通行。 这导致 第3, 4 条路将必须关闭。 1, 3, 4 道路无法通行。 S_1=8 。因此 输出 8 。 来自

2 今年 S_1 \oplus 10 = 2 由于灾难, 2 道路无法通行。 没有新的道路需要关闭。因此 2 。 来自