Regional 2022 Day1 E. Tree

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define pb push_back
#define mp make_pair

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

const int N = (int)5e4 + 111;
const int INF = (int)1e18;
const int md = (int)1e9 + 7;

vector<int> g[N];
int a[N];
int basis[N][21];
int pr[N];
int sz[N];

void add(int v,int x){
    if(x == 0)
        return;
    for(int i = 19; i >= 0; i--)
        x = min(x,basis[v][i]^x);
    for(int i = 19; i >= 0; i--){
        if((x&(1ll<<i)) == 0){
            basis[v][i] = min(basis[v][i],x^basis[v][i]);
            continue;
        }
        if(basis[v][i] == 0){
            basis[v][i] = x;
            sz[v]++;
            return;
        }
        x = basis[v][i]^x;
    }
    return;
}
void recalc(int v){
    for(int i = 0; i <= 19; i++)
        basis[v][i] = 0;
    sz[v] = 0;
    for(auto& x : g[v]){
        if(x == pr[v])
            continue;
        for(int i = 0; i <= 19; i++)
            add(v,basis[x][i]);
    }
    return;
}
void recalcALL(int v){
    while(v > 0){
        recalc(v);
        add(v,a[v]);
        v = pr[v];
    }
    return;
}
bool canBeRepresented(int v,int x){
    for(int i = 19; i >= 0; i--)
        x = min(x,x^basis[v][i]);
    return x == 0;
}
int getKth(int v,int k){
    if(k > (1ll << sz[v]))
        return -1;
    int ans = 0;
    k--;
    int cur = sz[v];
    for(int i = 19; i >= 0; i--){
        if(basis[v][i] == 0)
            continue;
        cur--;
        if(k >= (1ll << cur)){
            k -= (1ll << cur);
            ans ^= basis[v][i];
        }
    }
    return ans;
}
void dfs(int v){
    for(auto& x : g[v]){
        if(x == pr[v])
            continue;
        pr[x] = v;
        dfs(x);
    }
    recalc(v);
    add(v,a[v]);
    return;
}

void solve(){
    int n,group;
    cin >> n >> group;
    for(int i = 1; i < n; i++){
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    dfs(1);
//    for(auto& x : basis[1]){
//        cerr << x << " ";
//    }
//    cerr << "\n";
//    for(int i = 0; i < 4; i++)
//        cerr << basis[1][i] << " ";
//    cerr << "\n";
//    cerr << "sz[1] = " << sz[1] << "\n";
//    cerr << getKth(1,11);
//    return;

    int q;
    cin >> q;
    while(q--){
        int tp;
        cin >> tp;
        if(tp == 1){ /// UPDATE
            int v,nw;
            cin >> v >> nw;
            a[v] = nw;
            recalcALL(v);
        } else {
            int v,k;
            cin >> v >> k;
//            cerr << "basis[" << v << "] = ";
//            for(auto& x : basis[v]){
//                cerr << x << " ";
//            }
//            cerr << "\n";
            cout << getKth(v,k) << "\n";
        }
    }

    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int tests = 1;
//    cin >> tests;
    for(int test = 1; test <= tests; test++){
        solve();
    }

    return 0;
}
/**
5 0
1 2
1 5
2 3
2 4
1 15 7 3
15

15 = 1111

**/