CF1980G Yasya and the Mysterious Tree

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$ 的总和也不超过 $2 \cdot 10^5$。

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

由 ChatGPT 4.1 翻译