1. 让我们异或吧
题目ID：20709必做题100分
最新提交：
Time Limit Exceeded
30 分
历史最高：
Time Limit Exceeded
30 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
异或是一种神奇的运算,大部分人把它总结成不进位加法.
在生活中 xor 运算也很常见。比如，对于一个问题的回答，是为 11，否为 00，那么：
（AA 是否是男生）xor（BB 是否是男生）＝ AA 和 BB 是否能够成为情侣
好了，现在我们来制造和处理一些复杂的情况。比如我们将给出一颗树，它很高兴自己有 NN 个结点。树的每条边上有一个权值。我们要进行 MM 次询问，对于每次询问，我们想知道某两点之间的路径上所有边权的异或值。
输入格式
输入文件第一行包含一个整数 NN ，表示这颗开心的树拥有的结点数。
以下有 N−1N−1 行，描述这些边，每行有3个数，u,v,wu,v,w，表示 uu 和 vv 之间有一条权值为 ww 的边。
接下来一行有一个整数 MM，表示询问数。
之后的 MM 行，每行两个数 u,vu,v，表示询问这两个点之间的路径上的权值异或值。输出格式
输出 MM 行，每行一个整数，表示异或值
样例
Input 1
5 1 4 9644 2 5 15004 3 1 14635 5 3 9684 3 2 4 5 4 1 1
Output 1
975 14675 0
数据范围
对于 40%40% 的数据，有 1≤N,M≤30001≤N,M≤3000；
对于 100%100% 的数据，有 1≤N,M≤1000001≤N,M≤100000。保证边权在
int范围内。
代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
struct box{
int x,num;//点，权值
};
vector<box> vec[100005];
bool vis[100005];
int ans[100005];
bool dfs(int x,int now,int put){
if(x==1){
ans[put]=now;
return 1;
}
bool flg=0;
for(auto i:vec[x]){
if(vis[i.x]){
continue;
}
vis[i.x]=1;
if(dfs(i.x,now^i.num,put)){
flg=1;
break;
}
vis[i.x]=0;
}
if(!flg){
return 0;
}
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n-1;i++){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
vec[u].push_back({v,w});
vec[v].push_back({u,w});
}
scanf("%lld",&m);
ans[1]=0;
for(int i=2;i<=n;i++){
dfs(i,0,i);
}
while(m--){
int u,v;
scanf("%lld%lld",&u,&v);
cout<<(ans[u]^ans[v])<<endl;
}
return 0;
}
/*
颠倒空格
*/