F Trees and XOR Queries Again （树链剖分）

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  2e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
const int N = 20;
struct VEC {
    int d[N];
    int siz=0;
    void insert(ll x) {
        while(x) {
            int p=__lg(x);
            if(!d[p]) {d[p]=x;siz++; break;}
            x^=d[p];
        }
    }
    bool find(int x) {
     while(x) {
            int p=__lg(x);
            if(!d[p]) {return false;}
            x^=d[p];
        }
        return true;
    }
    void insert( VEC &b) {
        for(int i=N-1; i>=0; i--) {
            if(b.d[i]) {
                insert(b.d[i]);
            }
        }
    }
};
VEC merge(VEC a,VEC b) {
    if(a.siz==N) {
        return a;
    }
    if(b.siz==N) {
        return b;
    }
    VEC c=a;
    c.insert(b);
    return c;
}
int siz[MAXN],f[MAXN],hson[MAXN],deep[MAXN],top[MAXN],dfn[MAXN],rdfn[MAXN],rak[MAXN],cnt;
VEC a[MAXN];
VEC RMQ[MAXN][20];
int n;
void init() {
    for(int i=1; i<=n; i++) {
        RMQ[i][0]=a[rak[i]];
    }
    for(int i=1; (1<<i)<=n; i++) {
        for(int j=1; j+(1<<i)-1<=n; j++) {
            RMQ[j][i]=merge(RMQ[j][i-1],RMQ[j+(1<<(i-1))][i-1]);
        }
    }
}
VEC RMQ_query(int l,int r) {
    int k=(int)(__lg((r-l+1)));
    return merge(RMQ[l][k],RMQ[r-(1<<k)+1][k]);
}
vector<int> adj[MAXN];
void tree_build(int u,int fa,int dep) {
    deep[u]=dep;
    siz[u]=1;
    f[u]=fa;
    hson[u]=0;
    for(auto &v:adj[u]) {
        if(v==fa) continue;
        tree_build(v,u,dep+1);
        siz[u]+=siz[v];
        if(hson[u]==0||siz[v]>siz[hson[u]]) hson[u]=v;
    }
}
void tree_decom(int u,int t) {
    top[u]=t;
    cnt++;
    dfn[u]=cnt;
    rak[cnt]=u;
    if(hson[u]!=0) {
        tree_decom(hson[u],t);
        for(auto &v:adj[u]) {
            if(hson[u]!=v&&v!=f[u]) tree_decom(v,v);
        }
    }
    rdfn[u]=cnt;
}
int b[MAXN];
void solve() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>b[i];
    for(int i=1; i<=n; i++) {
        a[i].insert(b[i]);
    }
    for(int i=1; i<n; i++) {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    tree_build(1,1,0);
    tree_decom(1,1);
    init();
    int q;
    cin>>q;
    for(int i=1; i<=q; i++) {
        int u,v,k;
        cin>>u>>v>>k;
        if(k==0){
            cout<<"YES\n";
            continue;
        }
        VEC ans;
        int flag=0;
        while(top[v]!=top[u]) {
            if(deep[top[u]]>deep[top[v]]) {
                if(flag)
                ans=merge(ans,RMQ_query(dfn[top[u]],dfn[u]));
                else{
                    flag=1;
                    ans=RMQ_query(dfn[top[u]],dfn[u]);
                }
                u=f[top[u]];
            } else {
                if(flag)
                ans=merge(ans,RMQ_query(dfn[top[v]],dfn[v]));
                else{
                    flag=1;
                    ans=RMQ_query(dfn[top[v]],dfn[v]);
                }
                v=f[top[v]];
            }
        }
        if(dfn[v]<dfn[u]) swap(u,v);
        if(flag)
        ans=merge(ans,RMQ_query(dfn[u],dfn[v]));
        else{
            ans=RMQ_query(dfn[u],dfn[v]);
        }
        
        if(ans.siz==N||ans.find(k)){
            cout<<"YES\n";
        }
        else cout<<"NO\n";
    }
    
}
signed main() {
    close;
    solve();
}