记录编号	593840	评测结果	AAAWAWWWWW
题目名称	[ICPC 2017西安区域赛]树上异或xor	最终得分	40
用户昵称	flyfree	是否通过	未通过
代码语言	C++	运行时间	0.835 s
提交时间	2024-09-17 17:17:06	内存使用	32.76 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 50010
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll n,q,s,idx;
ll pv[50];
ll ed[MAXN*2],hd[MAXN],nxt[MAXN*2];
ll val[MAXN],f[MAXN][50],sum[MAXN][250],dep[MAXN];
void build(ll x,ll y){
    nxt[++idx]=hd[x];
    ed[idx]=y;
    hd[x]=idx;
}
ll lowbit(ll now){
    return now&(-now);
}
ll re_(ll now,ll h){
    ll p=now;
//    h--;
    while(h>0){
        p=f[p][lowbit(h)-1];
        h-=lowbit(h);
    }
    return p;
}
void dfs(ll now,ll fa){
    f[now][0]=fa,dep[now]=dep[fa]+1;
    for(int i=1;i<=20;i++){
        f[now][i]=f[f[now][i-1]][i-1];
    }
    for(int i=1;i<=s;i++){
        sum[now][i]=sum[re_(now,i)][i]^val[now];
    }
    for(int i=hd[now];i;i=nxt[i]){
        ll y=ed[i];
        if(y==fa)continue;
        dfs(y,now);
    }
}
ll re_lca(ll p,ll q,ll &l1,ll &l2){
    ll g=0;
    if(dep[p]<dep[q]){
        swap(p,q);
        g=1;
    }
    for(int i=20;i>=0;i--){
        if(dep[f[p][i]]>=dep[q]){
            p=f[p][i];
            l1+=pv[i];
        }
    }
    if(g)swap(l1,l2);
    if(p==q)return p;
    for(int i=20;i>=0;i--){
        if(f[p][i]!=f[q][i]){
            p=f[p][i],q=f[q][i];
            l1+=pv[i],l2+=pv[i];
        }
    }
    l1++,l2++;
    return f[p][0];
}
int main(){
    freopen("xor_xian.in","r",stdin);
    freopen("xor_xian.out","w",stdout);
    n=read(),q=read();
    s=pow(n,0.5);
    for(int i=1;i<n;i++){
        ll x=read(),y=read();
        build(x,y);
        build(y,x);
    }
    for(int i=1;i<=n;i++)val[i]=read();
    pv[0]=1;
    for(int i=1;i<=20;i++)pv[i]=pv[i-1]*2;
    dfs(1,0);
    for(int i=1;i<=q;i++){
        ll x=read(),y=read(),k=read(),l1=0,l2=0;
        ll lca=re_lca(x,y,l1,l2);
        if(k<=s){
            y=re_(y,(l1+l2)%k);
//            cout<<l1<<" "<<l2<<endl;
//            cout<<sum[x][k]<<" "<<sum[y][k]<<" "<<x<<" "<<y<<endl;
            cout<<(sum[x][k]^sum[y][k]^((l1%k)==0?val[lca]:0))<<endl;
//              cout<<"1 "<<(sum[x][k]^sum[y][k])<<endl;
        }else{
            ll ans=0;
            y=re_(y,(l1+l2)%k);
            while(dep[x]>=dep[lca]){
                ans=ans^val[x];
                x=re_(x,k);
            }
            while(dep[y]>dep[lca]){
                ans=ans^val[y];
                y=re_(y,k);
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}