Codeforces Round 950 (Div. 3)G. Yasya and the Mysterious Tree（字典树处理区间异或值）

Problem - G - Codeforces

存个字典树板子。

  1 #include <bits/stdc++.h>
  2 
  3 using i64 = long long;
  4 
  5 constexpr int N = 1E7;
  6 
  7 int trie[N][2];
  8 int cnt[N][2];
  9 
 10 int tot = 0;
 11 int newNode() {
 12     int x = ++tot;
 13     trie[x][0] = trie[x][1] = 0;
 14     cnt[x][0] = cnt[x][1] = 0;
 15     return x;
 16 }
 17 
 18 void add(int x, int d, int t = 1) {
 19     int p = 1;
 20     cnt[p][d] += t;
 21     for (int i = 29; i >= 0; i--) {
 22         int u = x >> i & 1;
 23         if (!trie[p][u]) {
 24             trie[p][u] = newNode();
 25         }
 26         p = trie[p][u];
 27         cnt[p][d] += t;
 28     }
 29 }
 30 
 31 int query(int x, int d) {
 32     int p = 1;
 33     if (!cnt[p][d]) {
 34         return 0;
 35     }
 36     int ans = 0;
 37     for (int i = 29; i >= 0; i--) {
 38         int u = x >> i & 1;
 39         if (cnt[trie[p][u ^ 1]][d]) {
 40             ans |= 1 << i;
 41             p = trie[p][u ^ 1];
 42         } else {
 43             p = trie[p][u];
 44         }
 45     }
 46     return ans;
 47 }
 48 
 49 void solve() {
 50     int n, m;
 51     std::cin >> n >> m;
 52     
 53     std::vector<std::vector<std::pair<int, int>>> adj(n);
 54     for (int i = 1; i < n; i++) {
 55         int u, v, w;
 56         std::cin >> u >> v >> w;
 57         u--, v--;
 58         adj[u].emplace_back(v, w);
 59         adj[v].emplace_back(u, w);
 60     }
 61     
 62     std::vector<int> a(n), d(n);
 63     auto dfs = [&](auto &&self, int x, int p) -> void {
 64         for (auto [y, w] : adj[x]) {
 65             if (y == p) {
 66                 continue;
 67             }
 68             d[y] = d[x] ^ 1;
 69             a[y] = a[x] ^ w;
 70             self(self, y, x);
 71         }
 72     };
 73     dfs(dfs, 0, -1);
 74     
 75     tot = 0;
 76     newNode();
 77     for (int i = 0; i < n; i++) {
 78         add(a[i], d[i]);
 79     }
 80     
 81     int w = 0;
 82     while (m--) {
 83         char o;
 84         std::cin >> o;
 85         
 86         if (o == '^') {
 87             int y;
 88             std::cin >> y;
 89             w ^= y;
 90         } else {
 91             int v, x;
 92             std::cin >> v >> x;
 93             v--;
 94             add(a[v], d[v], -1);
 95             int ans = std::max(query(a[v] ^ x, d[v]), query(a[v] ^ x ^ w, d[v] ^ 1));
 96             add(a[v], d[v]);
 97             std::cout << ans << " ";
 98         }
 99     }
100     std::cout << "\n";
101 }
102 
103 int main() {
104     std::ios::sync_with_stdio(false);
105     std::cin.tie(nullptr);
106     std::cout.tie(nullptr);
107     
108     int t;
109     std::cin >> t;
110     
111     while (t--) {
112         solve();
113     }
114     
115     return 0;
116 }