153还有救吗

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_BIT = 29;
const int MAXN = 200010;
using ll = long long;

struct Trie {
    struct Node {
        int son[2];
        int cnt;
        Node() {
            son[0] = son[1] = -1;
            cnt = 0;
        }
    };
    vector<Node> tree;

    Trie() {
        tree.clear();
        tree.emplace_back();
    }

    void insert(ll num) {
        int u = 0;
        for (int i = MAX_BIT; i >= 0; --i) {
            int b = (num >> i) & 1;
            if (tree[u].son[b] == -1) {
                tree.emplace_back();
                tree[u].son[b] = tree.size() - 1;
            }
            u = tree[u].son[b];
            tree[u].cnt++;
        }
    }

    void del(ll num) {
        int u = 0;
        for (int i = MAX_BIT; i >= 0; --i) {
            int b = (num >> i) & 1;
            if (tree[u].son[b] == -1) return; // 防越界
            u = tree[u].son[b];
            tree[u].cnt--;
        }
    }

    ll query(ll x) {
        ll res = 0;
        int u = 0;
        for (int i = MAX_BIT; i >= 0; --i) {
            int b = (x >> i) & 1;
            int want = 1 - b;
            if (tree[u].son[want] != -1 && tree[tree[u].son[want]].cnt > 0) {
                res |= (1LL << i);
                u = tree[u].son[want];
            } else {
                if (tree[u].son[b] == -1) break; // 防越界
                u = tree[u].son[b];
            }
        }
        return res;
    }
};

vector<pair<int, ll>> g[MAXN];
ll d[MAXN];
int dep[MAXN];

// 修正后的BFS
void bfs(int root, int n) {
    for (int i = 1; i <= n; i++) {
        dep[i] = -1; // 标记未访问 -1，不再用0区分
        d[i] = 0;
    }
    queue<int> q;
    q.push(root);
    dep[root] = 0;
    d[root] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto &edge : g[u]) {
            int v = edge.first;
            ll w = edge.second;
            if (dep[v] == -1) { // 未访问才走，完美规避回头父节点
                dep[v] = dep[u] + 1;
                d[v] = d[u] ^ w;
                q.push(v);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        // 清空邻接表
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 1; i < n; i++) {
            int u, v; ll w;
            cin >> u >> v >> w;
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }
        bfs(1, n);
        Trie trie0, trie1;
        for (int i = 1; i <= n; i++) {
            if (dep[i] % 2 == 0) trie0.insert(d[i]);
            else trie1.insert(d[i]);
        }
        ll tag = 0;
        while (m--) {
            char op;
            cin >> op;
            if (op == '^') {
                ll y;
                cin >> y;
                tag ^= y;
            } else {
                int v; ll x;
                cin >> v >> x;
                int dv = dep[v] % 2;
                ll sv = d[v];
                ll Sv = sv ^ (dv ? tag : 0);
                ll T = Sv ^ x;

                // 临时删除自身
                if (dv == 0) trie0.del(sv);
                else trie1.del(sv);

                ll max0 = trie0.query(T);
                ll max1 = trie1.query(T ^ tag);
                ll ans = max(max0, max1);

                // 恢复
                if (dv == 0) trie0.insert(sv);
                else trie1.insert(sv);

                cout << ans << ' ';
            }
        }
        cout << '\n';
    }
    return 0;
}