# 解题思路
两点之间的路径的话一定经过它们两个 LCA，这一点已经是显而易见的，那么再来看看异或的性质。
$$a\ xor\ b\ xor\ b = a\\ a\ xor\ a=0\\ a\ xor\ 0 = a\\ a\ xor\ b = b\ xor\ a\\ a\ xor\ b\ xor\ c = a\ xor\ (b\ xor\ c)$$
再回到这个题上来，因为 $a\ xor\ b\ xor\ b = a$，所以从根节点出来的一条路径我们可以预先处理一个异或和出来。
在询问的时候再将多余的路径给异或掉。设两点的 LCA 为 z，那么答案就是 $dis[tmp]\ xor\ dis[x]\ xor\ dis[tmp]\ xor\ dis[y]$
有第一条性质 $a\ xor\ b\ xor\ b = a$ 可以化简上式，答案就变成了 $dis[x]\ xor\ dis[y]$，化简后我们发现根本就不需要求 LCA。
下面给出代码。
# 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn = 1e5+
3;
int n, m, head[maxn], cnt, dis[maxn], rt =
1, fa[maxn][
32];
struct edge {
int to, w, nxt;} ed[maxn <<
1];
void read(
int &
x) {
x =
0;
int f =
1;
char c =
getchar();
while (c <
'0' || c >
'9') {
if(c ==
'-') f = -
1; c =
getchar();}
while (c <=
'9' && c >=
'0') {x = x*
10 + c-
'0'; c =
getchar();}
x *=
f;
}
struct HAHA {
void addedge(
int u,
int v,
int w) {
ed[++cnt].nxt = head[u], head[u] = cnt, ed[cnt].to = v, ed[cnt].w =
w;
}
void dfs(
int u) {
for(
int i=head[u]; i; i=
ed[i].nxt) {
if(ed[i].to == fa[u][
0])
continue;
dis[ed[i].to] = dis[u] ^
ed[i].w;
fa[ed[i].to][0] =
u;
dfs(ed[i].to);
}
}
}T;
int main() {
read(n);
int x, y, z;
for(
int i=
1; i<n; i++
) {
read(x), read(y), read(z);
T.addedge(x, y, z), T.addedge(y, x, z);
}
T.dfs(rt);
read(m);
for(
int i=
1; i<=m; i++
) {
read(x), read(y);
printf("%d\n", dis[x]^
dis[y]);
}
}
转载于:https://www.cnblogs.com/bljfy/p/9776058.html
