Steven_MengのBlog

传送门

考虑异或的性质,我们发现两个相同的数放在一起异或就会抵消,所以我们预处理这个节点到根的路径上的所有边的异或和$dis$,查询时发现$lca(u,v)$以上的那部分会抵消,于是答案就是$dis[u]$ $\rm xor$ $dis[v]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct Edge{
int to,len;
};
vector<Edge>G[MAXN];
inline void AddEdge(int u,int v,int w){
G[u].push_back(Edge{v,w});
}
int dis[MAXN];
void dfs(int u,int father){
for (register int i=0;i<G[u].size();++i){
int v=G[u][i].to,w=G[u][i].len;
if (v!=father){
dis[v]=dis[u]^w;
dfs(v,u);
}
}
}
int main(){
int n=read();
for (register int i=1;i<n;++i){
int u=read(),v=read(),w=read();
AddEdge(u,v,w);
AddEdge(v,u,w);
}
dfs(1,1);
int m=read();
while (m--){
int u=read(),v=read();
printf("%d\n",dis[u]^dis[v]);
}
}

 评论