Easiest HLD with Subtree Queries

 

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int maxn = 1E5 + 5;
const int logn = 19;
 
int tnode;
int tquery;
vector<vector<int>> graph;
vector<vector<int>> Tree;
int arr[maxn];
int subtreeSize[maxn];
int depth[maxn];
int father[maxn][logn];
int nxt[maxn];
int in[maxn];
int out[maxn];
int tym;
 
void makeTree(int u = 1, int p = 0) {
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        Tree[u].push_back(v);
        makeTree(v, u);
    }
}
 
void dfsSize(int u = 1) {
    subtreeSize[u] = 1;
    for (int &v : Tree[u]) {
        dfsSize(v);
        subtreeSize[u] += subtreeSize[v];
        if (subtreeSize[v] > subtreeSize[ Tree[u][0] ]) {
            swap(v, Tree[u][0]);
        }
    }
}
 
void dfs(int u = 1, int lvl = 1) {
    depth[u] = lvl;
    for (int i = 1; i < logn; i++) {
        father[u][i] = father[ father[u][i - 1] ][i - 1];
    }
    for (int v : Tree[u]) {
        father[v][0] = u;
        dfs(v, lvl + 1);
    }
}
 
void hld(int u = 1) {
    in[u] = ++tym;
    for (int v : Tree[u]) {
        nxt[v] = v == Tree[u][0] ? nxt[u] : v;
        hld(v);
    }
    out[u] = tym;
}
 
int findLca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (depth[ father[u][i] ] >= depth[v]) {
            u = father[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (father[u][i] != father[v][i]) {
            u = father[u][i];
            v = father[v][i];
        }
    }
    return father[u][0];
}
 
#define lchild  node * 2
#define rchild  node * 2 + 1
#define mid     (a + b) / 2
 
int STree[maxn * 4];
 
void update(int node, int a, int b, int pos, int val) {
    if (a > b or a > pos or b < pos) {
        return;
    }
    if (a >= pos and b <= pos) {
        STree[node] = val;
        return;
    }
    update(lchild, a, mid, pos, val);
    update(rchild, mid + 1, b, pos, val);
    STree[node] = STree[lchild] ^ STree[rchild];
}
 
int query(int node, int a, int b, int i, int j) {
    if (a > b or a > j or b < i) {
        return 0;
    }
    if (a >= i and b <= j) {
        return STree[node];
    }
    int p = query(lchild, a, mid, i, j);
    int q = query(rchild, mid + 1, b, i, j);
    return p ^ q;
}
 
int queryUp(int u, int v) {
    // v = lca
    int xorsum = 0;
    int L = in[v];
    while (true) {
        int l = in[ nxt[u] ];
        int r = in[u];
        if (l <= L) {
            l = max(l, L);
            xorsum ^= query(1, 1, tnode, l, r);
            break;
        }
        xorsum ^= query(1, 1, tnode, l, r);
        u = father[ nxt[u] ][0];
    }
    return xorsum;
}
 
int queryHld(int u, int v) {
    int lca = findLca(u, v);
    int lft = queryUp(u, lca);
    int rgt = queryUp(v, lca);
    int middle = queryUp(lca, lca);
    return lft ^ rgt ^ middle;
}
 
void updateHld(int u, int val) {
    arr[u] = val;
    update(1, 1, tnode, in[u], val);
}
 
void init() {
    graph.clear(); graph.resize(maxn);
    Tree.clear(); Tree.resize(maxn);
    tym = 0;
    for (int i = 0; i < maxn; i++) {
        subtreeSize[i] = 0;
        in[i] = 0;
        out[i] = 0;
        nxt[i] = 0;
        memset(father, 0, sizeof father[i]);
        depth[i] = 0;
    }
    memset(STree, 0, sizeof STree);
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    int tc;
    cin >> tc;
    while (tc--) {
        init();
 
        cin >> tnode;
        for (int i = 1; i <= tnode; i++) {
            cin >> arr[i];
        }
        for (int e = 1; e < tnode; e++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        makeTree();
        dfsSize();
        dfs();
        nxt[1] = 1;
        hld();
 
        for (int i = 1; i <= tnode; i++) {
            updateHld(i, arr[i]);
        }
 
        cin >> tquery;
        while (tquery--) {
            int type;
            cin >> type;
            if (type == 1) {
                int u, val;
                cin >> u >> val;
                updateHld(u, val);
            } else {
                int u, v;
                cin >> u >> v;
                int xorsum = queryHld(u, v);
                cerr << xorsum << " ";
                cout << (xorsum ? "Alice" : "Bob") << endl;
            }
        }
    }
}