武侍乐队

考点：可持久化01树，LCA，贪心
对整个图建可持久化01树，其父版本是图上的父亲
对于每次询问，LCA得出其最近公共祖先
利用01树找到表演风格相差最大的城市
利用差分求出其他城市的异或和
最后通过贪心计算答案

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int tot;
int cnt;
int x[N];
int n,m,w;
int head[N];
int tr[N<<6][2];
int f[N][20],dep[N];
int siz[N<<6],Xor[N],rt[N];
struct Edge{
    int u,v;
}edge[N<<1];
void add(int x,int y){
    edge[++tot].u=head[x];
    edge[tot].v=y;
    head[x]=tot;
    return ;
}
void insert(int now,int pre,int val){
    for(int i=1<<30; i; i>>=1){
        bool k=val&i;
        tr[now][k^1]=tr[pre][k^1];
        tr[now][k]=cnt++;
        siz[tr[now][k]]=siz[tr[pre][k]]+1;
        now=tr[now][k];
        pre=tr[pre][k];
    }
}
void dfs(int now,int fa){
    f[now][0]=fa;
    dep[now]=dep[fa]+1;
    Xor[now]=Xor[fa]^x[now];
    for(int i=1; i<20; ++i) f[now][i]=f[f[now][i-1]][i-1];
    for(int i=head[now]; i; i=edge[i].u){
        int to=edge[i].v;
        if(to==fa) continue;
        rt[to]=cnt++;
        insert(rt[to],rt[now],x[to]);
        dfs(to,now);
    }
}
int query(int now,int pre,int val){
    int res=0;
    for(int i=1<<30; i; i>>=1){
        bool k=val&i;
        if(siz[tr[pre][k^1]]>siz[tr[now][k^1]]){
            res+=i;
            now=tr[now][k^1];
            pre=tr[pre][k^1];
        }else{
            now=tr[now][k];
            pre=tr[pre][k];
        }
    }
    return res;
}
int LCA(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19; i>=0; --i){
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
        if(x==y) return x;
    }
    for(int i=19; i>=0; --i)
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    return f[x][0];
}
int solve(int u,int v,int p){
    int lca=LCA(u,v);
    int maxx=0,ans=0;
    int res=Xor[u]^Xor[v];
    maxx=max(maxx,query(rt[lca],rt[u],p));
    maxx=max(maxx,query(rt[lca],rt[***    maxx=max(maxx,x[lca]^p);
    res=res^x[lca]^maxx^p;
    for(int i=30; i>=0; --i){
        if((ans|(1<<i))>w) continue;
        if(res&(1<<i)) continue;
        ans|=(1<<i);
    }
    return ans|res;
}
int main(){
    scanf("%d%d%d",&n,&m,&w);
    for(int i=1,p,q; i<n; ++i){
        scanf("%d%d",&p,&q);
        add(p,q);
        add(q,p);
    }
    for(int i=1; i<=n; ++i) scanf("%d",&x[i]);
    cnt=1;
    rt[1]=cnt++;
    insert(rt[1],0,x[1]);
    dfs(1,0);
    for(int i=1,u,v,s; i<=m; ++i){
        scanf("%d%d%d",&u,&v,&s);
        printf("%d\n",solve(u,v,s));
    }
    return 0;
}