题解 p2420 让我们异或吧

佚名 6年前 (2019-04-26) 随笔 1408人围观抢沙发百度已收录

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int N=100005;int x,y,z;
 6 int n,m,k=0,head[N],dis[N];bool vis[N];
 7 struct node{int to,next,w;}edge[N<<1];
 8 //无向图存边数组开两倍 
 9 void add(int u,int v,int w){
10     edge[++k].to=v;edge[k].next=head[u];edge[k].w=w;head[u]=k;
11 }
12 void dfs(int now,int val){
13     //dis[tmp]^dis[tmp]^dis[u]^dis[v]=dis[u]^dis[v]
14     //所以只要求每一个和根节点的异或值就可以了 
15     dis[now]=val;vis[now]=true;
16     //now到根节点的异或边权即为val
17     //这个点已经找过了 
18     for(register int i=head[now];i;i=edge[i].next){
19         //从这个点所在的图的边的起点开始向后找 
20         if(!vis[edge[i].to]) dfs(edge[i].to,val^edge[i].w);
21         //如果在这个没有搜过，就顺着向下搜，异或值就是现在的^要走过的 
22     }
23 }
24 int main(){
25     scanf("%d",&n);
26     for(register int i=1;i<=n-1;i++){
27         scanf("%d%d%d",&x,&y,&z);
28         add(x,y,z);add(y,x,z);
29     }
30     dfs(1,0);/*从根节点开始找，根节点和自己的异或值就是零*/scanf("%d",&m);
31     for(register int i=1;i<=m;i++){
32         scanf("%d%d",&x,&y);
33         printf("%d\n",dis[x]^dis[y]);
34     } 
35 }