← 返回题目列表

Codeforces · 1980/G

G. 亚西亚和神秘树

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

Yasya 在森林里散步,无意中发现了一棵有 $$$n$$$ 个顶点的树。树是一个无环的连通无向图。

在树旁边,女孩发现了一份古老的手稿,上面写着$$$m$$$的疑问。查询可以有两种类型。

第一种类型的查询由整数 $$$y$$$ 描述。树中每条边的权重由该边的权重与整数 $$$y$$$ 的按位异或替换。

第二种类型由顶点$$$v$$$和整数$$$x$$$描述。 Yasya 选择一个顶点 $$$u$$$ ($$$1 \le u \le n$$$, $$$u \neq v$$$) 并在树中绘制一条从 $$$v$$$ 到 $$$u$$$ 的双向权重 $$$x$$$ 边。

然后 Yasya 在结果图中找到一个简单的循环,并计算其中所有边的按位异或。她想要选择一个顶点 $$$u$$$ 使得计算值最大。该计算值将是查询的答案。可以证明这样的循环存在并且在给定约束下是唯一的(与 $$$u$$$ 的选择无关)。如果 $$$v$$$ 和 $$$u$$$ 之间已经存在边,则简单的循环是路径 $$$v \to u \to v$$$。

请注意,第二种类型的查询是在心理上执行的,这意味着树在其之后不会发生任何变化。

帮助 Yasya 回答所有问题。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — 树中的顶点数和查询数。

每个测试用例接下来的 $$$n - 1$$$ 行包含三个整数 $$$v$$$、$$$u$$$、$$$w$$$ ($$$1 \le v, u \le n$$$, $$$1 \le w \le 10^9$$$) — 树中某些边的末端及其权重。

保证给定的边集形成一棵树。

每个测试用例接下来的 $$$m$$$ 行描述了查询:

- ^ $$$y$$$ ($$$1 \le y \le 10^9$$$) — 第一类型查询的参数;
- ? $$$v$$$ $$$x$$$ ($$$1 \le v \le n$$$, $$$1 \le x \le 10^9$$$) — 第二种类型查询的参数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。 $$$m$$$ 也能保证同样的效果。

输出

对于每个测试用例,输出第二类型查询的答案。

示例

输入 #1

2
3 7
1 2 1
3 1 8
^ 5
? 2 9
^ 1
? 1 10
^ 6
? 3 1
? 2 9
5 6
1 2 777
3 2 2812
4 1 16
5 3 1000000000
^ 4
? 3 123
? 5 1000000000
^ 1000000000
? 1 908070
? 2 1

输出 #1

13 15 11 10 
1000000127 2812 999756331 999999756

输入 #2

3
8 4
8 6 3
6 3 4
2 5 4
7 6 2
7 1 10
4 1 4
5 1 2
^ 4
^ 7
? 7 8
? 4 10
5 6
3 1 4
2 3 9
4 3 6
5 2 10
? 5 7
^ 1
^ 8
? 4 10
? 1 9
? 3 6
4 2
2 1 4
4 3 5
2 3 4
^ 13
? 1 10

输出 #2

14 13 
13 8 11 11 
10