#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; const int LOG_VAL = 30; struct QueryInfo { int id; // ID của truy vấn (để in ra đúng thứ tự) int type; // 0: Add, 1: Query int u; // Add: node index, Query: start node a int v; // Add: weight, Query: subtree node b int time_added; // Add: thời điểm thêm (node ID) }; int n = 1, q; vector<pair<int, int>> adj[MAXN]; int st[MAXN], en[MAXN], D[MAXN]; // D[u] là XOR path từ root đến u int timer; int ans[MAXN]; // Lưu kết quả truy vấn vector<QueryInfo> queries; // DFS để linearize cây (Euler tour) và tính XOR path void dfs(int u, int p) { st[u] = ++timer; for (auto &edge : adj[u]) { int v = edge.first; int w = edge.second; if (v != p) { D[v] = D[u] ^ w; dfs(v, u); } } en[u] = timer; } struct Node { Node *child[2]; int cnt; Node() { child[0] = child[1] = NULL; cnt = 0; } }; Node* null; void init_trie() { null = new Node(); null->child[0] = null->child[1] = null; null->cnt = 0; } void insert(Node* prev, Node* &curr, int val) { curr = new Node(); *curr = *prev; curr->cnt++; Node* p = curr; for (int i = LOG_VAL; i >= 0; i--) { int bit = (val >> i) & 1; p->child[bit] = new Node(); *p->child[bit] = *prev->child[bit]; p->child[bit]->cnt++; p = p->child[bit]; prev = prev->child[bit]; } } int query(Node* verL, Node* verR, int val) { int res = 0; for (int i = LOG_VAL; i >= 0; i--) { int bit = (val >> i) & 1; int want = 1 - bit; if (verR->child[want]->cnt - verL->child[want]->cnt > 0) { res += (1 << i); verR = verR->child[want]; verL = verL->child[want]; } else { verR = verR->child[bit]; verL = verL->child[bit]; } } return res; } Node* roots[MAXN]; void solve_cdq(int l, int r, vector<int>& q_indices) { if (q_indices.empty()) return; if (l == r) return; int mid = (l + r) >> 1; vector<int> left_q, right_q; for (int id : q_indices) { if (queries[id].id <= mid) left_q.push_back(id); else right_q.push_back(id); } solve_cdq(l, mid, left_q); solve_cdq(mid + 1, r, right_q); vector<pair<int, int>> nodes_to_add; for (int id : left_q) { if (queries[id].type == 0) { int u = queries[id].time_added; nodes_to_add.push_back({st[u], D[u]}); } } if (l == 1) nodes_to_add.push_back({st[1], D[1]}); sort(nodes_to_add.begin(), nodes_to_add.end()); vector<Node*> versions; vector<int> version_st; Node* current_root = null; versions.push_back(null); version_st.push_back(0); for (auto p : nodes_to_add) { int pos = p.first; int val = p.second; Node* new_root; insert(current_root, new_root, val); current_root = new_root; versions.push_back(current_root); version_st.push_back(pos); } for (int id : right_q) { if (queries[id].type == 1) { int u = queries[id].u; int b = queries[id].v; auto itR = upper_bound(version_st.begin(), version_st.end(), en[b]); int idxR = prev(itR) - version_st.begin(); auto itL = upper_bound(version_st.begin(), version_st.end(), st[b] - 1); int idxL = prev(itL) - version_st.begin(); int val = query(versions[idxL], versions[idxR], D[u]); ans[id] = max(ans[id], val); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); init_trie(); cin >> q; int node_cnt = 1; queries.resize(q + 1); for (int i = 1; i <= q; i++) { string type; int u, v; cin >> type >> u >> v; queries[i].id = i; if (type == "Add") { queries[i].type = 0; queries[i].u = u; queries[i].v = v; node_cnt++; queries[i].time_added = node_cnt; adj[u].push_back({node_cnt, v}); adj[node_cnt].push_back({u, v}); } else { queries[i].type = 1; queries[i].u = u; queries[i].v = v; ans[i] = 0; } } D[1] = 0; dfs(1, 0); vector<int> q_indices; for(int i = 1; i <= q; i++) q_indices.push_back(i); solve_cdq(1, q, q_indices); for (int i = 1; i <= q; i++) if (queries[i].type == 1) cout << ans[i] << "\n"; return 0; }