F - Trees and XOR Queries Again

上课闲着无聊娱乐看了一眼，太典了，没忍住写了下

本质上就是问树上一条链上能不能xor出一个给定值，2e5级别

众所周知，线性基可以解决任意个数能不能xor出给定值

众所周知，线性基可以通过B^2的复杂度合并，所以你甚至可以上树剖，每个线段树的节点维护一个线性基，那么这样是O(nlogn^2B^2)，可能也能过吧，IDK

当然其实这个问题非常老套，有一个也许稍微冷门一点但是依旧广为人知的事情就是线性基是可以替换的，把问题退化到序列上的区间查询，对于一个以r为右端点的线性基，我们肯定希望基里面的元素尽可能靠右，所以我们可以通过替换一直更新线性基，让线性基更“优秀”，那么迁移到树上其实就是希望元素的深度尽可能深，对于一个查询，我们把（u，v）两个节点的线性基O(B^2）合并，那么我们真正的基就是合并后的基中深度不比LCA小的那些元素，然后就直接查询就行了，O(nlogn + nB^2）

可能这个是最优做法，如果你写点分治啥的遇到在线就不行了，复杂度也是最低了感觉

为什么突然想写了，因为感觉真的太典了，感觉出了好几次了，但是竟然在CF还是见到了，心血来潮写了

#include <bits/stdc++.h>
#include <random>

#define MP make_pair
#define pb push_back
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

using namespace std;
using LL = long long;
using ULL = unsigned long long;

const int maxn = 4e5 + 5;
const int maxk = 22;

int n;
int A[maxn];
int dep[maxn];
int fa[maxn][maxk];
vector<int> E[maxn];

struct linear_base{
    int base[maxk];
    int dep[maxk];

    void insert(int x, int d){
        for(int i = maxk - 1; i >= 0; --i){
            int b = ((x >> i) & 1);
            if(b){
                if(!base[i]){
                    base[i] = x;
                    dep[i] = d;
                    return;
                }
                else{
                    if(dep[i] < d){
                        swap(dep[i], d);
                        swap(base[i], x);
                    }
                }
                x ^= base[i];
            }
        }
    }

    void operator = (const linear_base &rhs){
        for(int i = 0; i < maxk; ++i){
            base[i] = rhs.base[i];
            dep[i] = rhs.dep[i];
        }
    }

    int query(int x, int d){
        for(int i = maxk - 1; i >= 0; --i){
            int b = ((x >> i) & 1);
            if(b && dep[i] >= d) 
                x ^= base[i];
        }
        return (x == 0);
    }

}B[maxn], tmp_base;

void merge(linear_base &a, linear_base &b)
{
    tmp_base = a;
    for(int i = 0; i < maxk; ++i){
        tmp_base.insert(b.base[i], b.dep[i]);
    }
}

void dfs(int x, int fr)
{
    B[x] = B[fr];
    B[x].insert(A[x], dep[x]);
    for(auto &v : E[x]){
        if(v == fr) continue;
        dep[v] = dep[x] + 1;
        fa[v][0] = x;
        dfs(v, x);
    }

    
}

int lca(int x, int y)
{
    if(dep[x] < dep[y])  swap(x, y);
    int d = dep[x] - dep[y];
    for(int i = maxk - i; i >= 0; --i){
        if(((d >> i) & 1)){
            x = fa[x][i];
        }
    }
    if(x == y)  return x;
    for(int i = maxk - 1; i >= 0; --i){
        if(fa[x][i] != fa[y][i]){
            x = fa[x][i], y = fa[y][i];
        }
    }
    return x == y ? x : fa[x][0];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> A[i];
    }
    for(int i = 1; i <= n - 1; ++i){
        int a, b;
        cin >> a >> b;
        E[a].pb(b), E[b].pb(a);
    }

    dfs(1, 0);
    for(int j = 1; j <= maxk - 1; ++j){
        for(int i = 1; i <= n; ++i){
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }

    int Q = 0;
    cin >> Q;
    while(Q--){
        int a, b, c;
        cin >> a >> b >> c;
        merge(B[a], B[b]);
        int l = lca(a, b);
        int ans = tmp_base.query(c, dep[l]);
        if(ans) cout << "YES\n";
        else cout << "NO\n";
    }

	return 0;
}