题目链接：

题意：

给你一棵有n个节点的树，然后有Q个询问，每次询问给出两个点x,y,k。将x->y路径上经过的点放进一个数组a里，将询问[0],a[k],a[2*k],a[m*k]的值异或起来的值为多少。

题解：

预处理lca和k=1的答案，k>1的用倍增暴力往上跳，然后就完了，不过有点慢，需要加个读入挂才能过。

 

1 #include
      
        2 #define F(i,a,b) for(int i=(a);i<=(b);++i) 3 using namespace std; 4  5 const int N=5e5+5,DEG=17; 6 int ed,g[N],nxt[2*N],v[2*N],fa[N][DEG],dep[N],val[N]; 7 int a[N],n,q,vis[N],TIM; 8  9 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}10 11 void dfs(int u,int pre){12     dep[u]=dep[pre]+1,fa[u][0]=pre,val[u]=val[pre]^a[u];13     F(i,1,DEG-1)fa[u][i]=fa[fa[u][i-1]][i-1];14     for(int i=g[u];i;i=nxt[i])if(v[i]!=pre)dfs(v[i],u);15 }16 17 int LCA(int a,int b){18     if(dep[a]>dep[b])a^=b,b^=a,a^=b;19     if(dep[a]
       
        <
        
         =0;i--)21     if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];22     return a;23 }24 25 26 int kth_father(int x,int k)27 {28     while(k)x=fa[x][__builtin_ctz(k&-k)],k^=k&-k;29     return x;30 }31 32 void solve(int x,int y,int k)33 {34     TIM++;35     if(x==y){printf("%d\n",a[x]);return;}36     int lca=LCA(x,y);37     if(k==1)38     {39         if(lca==x)printf("%d\n",val[y]^val[lca]^a[lca]);40         else if(lca==y)printf("%d\n",val[x]^val[lca]^a[lca]);41         else printf("%d\n",val[y]^val[x]^a[lca]);42         return;43     }44     int now=kth_father(x,k),ans=a[x],pre=now;45     vis[x]=TIM;46     while(dep[now]>=dep[lca])47     {48         if(vis[now]!=TIM)ans^=a[now],vis[now]=TIM;49         pre=now,now=kth_father(now,k);50     }51     int Long=dep[x]+dep[y]-2*dep[lca]+1;52     if((Long-1)
         
          =dep[lca])ans^=a[now],vis[now]=TIM;57     now=kth_father(now,k);58     while(dep[now]>=dep[lca])59     {60         if(vis[now]!=TIM)ans^=a[now],vis[now]=TIM;61         now=kth_father(now,k);62     }63     printf("%d\n",ans);64 }65 66 int main(){67     while(read(n),read(q))68     {69         int x,y,k;70         F(i,1,n)g[i]=0;ed=0;71         F(i,2,n)72         {73             read(x),read(y);74             adg(x,y),adg(y,x);75         }76         F(i,1,n)read(a[i]);77         dfs(1,0);78         F(i,1,q)79         {80             read(x),read(y),read(k);81             solve(x,y,k);82         }83     }84     return 0;85 }