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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath> 
using namespace std;
int q,a[50010],fa[50010][20],s[50010][250],nxt[100010],to[100010],head[100010],tot,sq,n,vis[50010],deep[50010];
void add(int u,int v)
{
    tot++;
    nxt[tot]=head[u];
    head[u]=tot;
    to[tot]=v;
}
int get(int now,int x)
{
    for(int i=17;i>=0;--i)
    {
        if(x>=(1<<i))
        {
           now=fa[now][i];
           x-=(1<<i);
        }
    }
    return now;
}
void dfs(int now)
{
    vis[now]=1;
    for(int i=1;i<=17;++i)
    {
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
    for(int i=1;i<=sq;++i)
    {
        s[now][i]=s[get(now,i)][i]^a[now];
    }
    for(int i=head[now];i;i=nxt[i])
    {
        if(!vis[to[i]])
        {
           fa[to[i]][0]=now;
           deep[to[i]]=deep[now]+1;
           dfs(to[i]);
        }
    }
}
int lca(int u,int v)
{
    for(int i=17;i>=0;--i)
    {
        if(deep[fa[u][i]]>=deep[v]) u=fa[u][i];
    }
    for(int i=17;i>=0;--i)
    {
        if(deep[fa[v][i]]>=deep[u])
        v=fa[v][i];
    }
    if(u==v) return u;
    for(int i=17;i>=0;--i)
    {
        if(fa[u][i]!=fa[v][i])
        {
           u=fa[u][i];
           v=fa[v][i];
        }
    }
    return fa[u][0];
}
int main()
{
    freopen("xor_xian.in","r",stdin);
    freopen("xor_xian.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    sq=sqrt(n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    } 
    deep[1]=1;
    dfs(1);
    for(int i=1;i<=q;++i)
    {
        int u,v,k;
        scanf("%d%d%d",&u,&v,&k);
        if(k<=sq)
        {
            int nowans=0;
            int l=lca(u,v);
            int l1=(deep[u]-deep[l])%k;
            int ll=get(l,k-l1);
            nowans^=s[u][k];
            nowans^=s[ll][k];
            int l2=(deep[v]-deep[l]);
            if(l2>=k-l1&&v!=l)
            {
                l2-=(k-l1);
                v=get(v,l2%k);
                l1=(deep[v]-deep[l])%k;
                if(l1==0) ll=l;
                else ll=get(l,k-l1);
                nowans^=s[v][k];
                nowans^=s[ll][k];
            }
            printf("%d\n",nowans);
        }
        else
        {
                 
            int nowans=0;
            int l=lca(u,v);
            int l1=(deep[u]-deep[l])%k;
            int ll=get(l,k-l1);
            int now=u;
            while(deep[now]>=deep[l])
            {
                nowans^=a[now];
                now=get(now,k);
            }
            int l2=(deep[v]-deep[l]);
            if(l2>=k-l1&&v!=l)
            {
                l2-=(k-l1);
                v=get(v,l2%k);
                now=v;
                while(deep[now]>deep[l])
                {
                    nowans^=a[now];
                    now=get(now,k);
                }
            }
            printf("%d\n",nowans);
        }
    }
    tot=0;
    for(int i=1;i<=n;++i)
    {
        head[i]=0;
        for(int j=1;j<=sq;++j)
        {
            s[i][j]=0;
        }   
        a[i]=0;
        vis[i]=0;
        deep[i]=0;
        for(int j=0;j<=17;++j)
        {
            fa[i][j]=0;
        } 
    }
    return 0;
}