CF938G Shortest Path Queries

给定一个无向连通带权图。两点之间某条路径的长度定义为该路径上所有边权的按位异或（如果某条边被多次经过，则它会被异或相应次数）。 你需要处理三种类型的操作： - $1\ x\ y\ d$ —— 在点 $x$ 和点 $y$ 之间添加一条权值为 $d$ 的边。保证在此操作前 $x$ 和 $y$ 之间没有边。 - $2\ x\ y$ —— 删除点 $x$ 和点 $y$ 之间的边。保证图中存在这条边，且删除后图仍然连通。 - $3\ x\ y$ —— 计算点 $x$ 到点 $y$ 的最短路径（可以不是简单路径）的长度。 对于所有类型为 $3$ 的操作，按顺序输出答案。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 200000$），分别表示图中点的数量和边的数量。 接下来 $m$ 行，每行包含三个整数 $x$、$y$ 和 $d$（$1 \leq x < y \leq n$，$0 \leq d \leq 2^{30}-1$），表示一条连接 $x$ 和 $y$ 的权值为 $d$ 的边。每对 $(x, y)$ 最多出现一次。初始图保证连通。 接下来一行包含一个整数 $q$（$1 \leq q \leq 200000$），表示操作的数量。 接下来 $q$ 行，每行表示一个操作，格式如下： - $1\ x\ y\ d$（$1 \leq x < y \leq n$，$0 \leq d \leq 2^{30}-1$）—— 在 $x$ 和 $y$ 之间添加一条权值为 $d$ 的边。保证此时 $x$ 和 $y$ 之间没有边。 - $2\ x\ y$（$1 \leq x < y \leq n$）—— 删除 $x$ 和 $y$ 之间的边。保证存在这条边，且删除后图仍然连通。 - $3\ x\ y$（$1 \leq x < y \leq n$）—— 计算 $x$ 到 $y$ 的最短路径（可以不是简单路径）的长度。 保证至少有一个操作是类型 $3$。

对于每个类型为 $3$ 的操作，按输入顺序输出答案。

由 ChatGPT 4.1 翻译