记录编号	450748	评测结果	AAAAAAAAAA
题目名称	[ICPC 2017西安区域赛]树上异或xor	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.380 s
提交时间	2017-09-16 18:01:16	内存使用	102.38 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int SIZEN=50010,SIZELOG=20,SIZEQ=510;
const int SQTN=500;
int N,Q,LOGN;
int A[SIZEN]={0};
vector<int> c[SIZEN];
int grand[SIZEN][SIZELOG]={0};
int depth[SIZEN]={0};
int gxor[SIZEN][SIZEQ]={0};
int jump_up(int a,int k){
    int pwd=1;
    for(int i=0;i<=LOGN;i++){
        if(k&pwd){
            a=grand[a][i];
            k^=pwd;
        }
        pwd<<=1;
        if(!k) break;
    }
    return a;
}
int LCA(int a,int b){//a和b的距离
	if(depth[a]>depth[b]) swap(a,b);//a在上面b在下面
	//上下不能弄反
	for(int i=LOGN;i>=0;i--) if(depth[a]<depth[b]&&depth[grand[b][i]]>=depth[a]) b=grand[b][i];
	for(int i=LOGN;i>=0;i--) if(grand[a][i]!=grand[b][i]) a=grand[a][i],b=grand[b][i];
	if(a!=b) a=grand[a][0],b=grand[b][0];//现在a和b再往上走一步就是LCA了
    //否则它们就是LCA,这个if不加会错
    return a;
}
int calc(int a,int k,int mndep){
    if(depth[a]<mndep) return 0;
    int h=depth[a]-mndep;
    int hp=((h/k)+1)*k;
    int a1=jump_up(a,hp);
    //cout<<a<<" "<<k<<" "<<h<<" "<<hp<<endl;
    //cout<<a<<" "<<k<<" "<<mndep<<" "<<hp<<" "<<(gxor[a][k]^gxor[a1][k])<<endl;
    return gxor[a][k]^gxor[a1][k];
}
int query(int a,int b,int k){
    int g=LCA(a,b);
    if(k<=SQTN){
        int r=(depth[a]+depth[b]-2*depth[g])%k;
        int b1=jump_up(b,r);
        int ans=calc(a,k,depth[g])^calc(b1,k,depth[g]+1);
        return ans;
    }
    else{
        int r=(depth[a]+depth[b]-2*depth[g])%k;
        b=jump_up(b,r);
        int ans=0;
        while(depth[a]>=depth[g]){
            ans^=A[a];
            a=jump_up(a,k);
        }
        while(depth[b]>depth[g]){
            ans^=A[b];
            b=jump_up(b,k);
        }
        return ans;
    }
}
void DFS(int x){
	for(int i=1;i<=LOGN;i++){
		grand[x][i]=grand[grand[x][i-1]][i-1];
		if(!grand[x][i]) break;
	}
    for(int i=1;i<=SQTN;i++) gxor[x][i]=A[x];
    //if(x==2) cout<<gxor[x][1]<<endl;
    int y=x;
    for(int i=1;i<=SQTN;i++){
        y=grand[y][0];
        if(!y) break;
        gxor[x][i]^=gxor[y][i];
    }
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i];
		if(u!=grand[x][0]){
			depth[u]=depth[x]+1;
			grand[u][0]=x;
			DFS(u);
		}
	}
}
void work(void){
    depth[0]=-1;
    depth[1]=0;
    DFS(1);
    /*for(int i=1;i<=N;i++){
        for(int j=1;j<=2;j++) cout<<gxor[i][j]<<" ";
        cout<<endl;
    }*/
    int a,b,k;
    for(int i=1;i<=Q;i++){
        scanf("%d%d%d",&a,&b,&k);
        printf("%d\n",query(a,b,k));
    }
}
bool read(void){
    if(scanf("%d%d",&N,&Q)==EOF) return false;
    LOGN = floor(log(N+0.0)/log(2.0));
    //SQTN = sqrt(N+1.0);
    for(int i=0;i<=N;i++){
        c[i].clear();
        depth[i]=0;
        for(int j=0;j<=LOGN;j++) grand[i][j]=0;
        for(int j=0;j<=SQTN;j++) gxor[i][j]=0;
    }
    for(int i=1;i<N;i++){
        int a,b;scanf("%d%d",&a,&b);
        c[a].push_back(b);
        c[b].push_back(a);
    }
    for(int i=1;i<=N;i++) scanf("%d",&A[i]);
    return true;
}
int main(){
    freopen("xor_xian.in","r",stdin);
    freopen("xor_xian.out","w",stdout);
    while(read()){
        work();
    }
    return 0;
}