[Codeforces1055F] Tree and XOR

(n) 个节点的树，有边权，路径长度为边权异或和。求 (n^2) 个点对之间路径长度的第 (k) 小（即 ((a, b),(b, a)) 算不同的两个，((a, a)) 的路径长度为 (0)）。

(n leq 10^6,val < 2^{62})。

记 (i) 到根的路径长度为 (d_i)，那么任意两点 ((i, j)) 的路径长度都可表示为 (d_i oplus d_j)。

问题转化为求可重集合 ({D:D=d_i oplus d_j, 1 leq i, j leq n}) 的第 (k) 小。

把 (d_i) 插入到 trie 里，从高位到低位考虑，如果 (D) 当前位为 (0) 的个数 (s geq k) 说明答案该为为 (0)，否则为 (1)。

(D) 的当前位为 (0/1) 即 (d_i oplus d_j = 0/1) 各有两种情况，乍一看每考虑一位状态数都会乘 2，但实际上每一层状态数最多都只有 (2n) 个。

考虑到当前位时答案的高位已经确定了，设为 (ans)，那么状态 (d_i) 只会和 (d_i oplus ans) 成对出现，所以最多有 (2n) 个状态。

由于 (n leq 10^6)，整个的 trie 存不下，所以像滚动数组一样，每次只存当前层的节点。

#include <bits/stdc++.h>
#ifdef LOCAL
#define dbg(args...) std::cerr << "33[32;1m" << #args << " -> ", err(args)
#else
#define dbg(...)
#endif
inline void err() { std::cerr << "33[0m
"; }
template<class T, class... U>
inline void err(const T &x, const U &... a) { std::cerr << x << ' '; err(a...); }
template <class T>
inline void readInt(T &w) {
  char c, p = 0;
  while (!isdigit(c = getchar())) p = c == '-';
  for (w = c & 15; isdigit(c = getchar());) w = w * 10 + (c & 15);
  if (p) w = -w;
}
template <class T, class... U>
inline void readInt(T &w, U &... a) { readInt(w), readInt(a...); }
template <class T, class U>
inline bool smin(T &x, const U &y) { return y < x ? x = y, 1 : 0; }
template <class T, class U>
inline bool smax(T &x, const U &y) { return x < y ? x = y, 1 : 0; }

typedef long long LL;
typedef std::pair<int, int> PII;

constexpr int N(1e6 + 5);

LL d[N];
int id[N], ch[N][2], siz[N];

int main() {
  int n; LL k;
  readInt(n, k);
  for (int i = 2, p; i <= n; i++) {
    readInt(p, d[i]), d[i] ^= d[p];
  }
  for (int i = 1; i <= n; i++) id[i] = 1;
  LL ans = 0;
  std::vector<PII> p = { PII(1, 1) }, np;
  for (int i = 61, c = 1, nc; ~i; i--, c = nc, p.swap(np)) {
    np.clear(), nc = 0;
    for (int j = 1; j <= c; j++) ch[j][0] = ch[j][1] = 0;
    for (int j = 1; j <= n; j++) {
      int k = d[j] >> i & 1;
      if (!ch[id[j]][k]) ch[id[j]][k] = ++nc, siz[nc] = 0;
      siz[id[j] = ch[id[j]][k]]++;
    }
    LL sum = 0;
    for (auto [x, y] : p) {
      sum += 1LL * siz[ch[x][0]] * siz[ch[y][0]] + 1LL * siz[ch[x][1]] * siz[ch[y][1]];
      if (sum >= k) break;
    }
    if (sum < k) {
      k -= sum, ans |= 1LL << i;
      for (auto [x, y] : p) {
        if (ch[x][0] && ch[y][1]) np.emplace_back(ch[x][0], ch[y][1]);
        if (ch[x][1] && ch[y][0]) np.emplace_back(ch[x][1], ch[y][0]);
      }
        
    } else {
      for (auto [x, y] : p) {
        if (ch[x][0] && ch[y][0]) np.emplace_back(ch[x][0], ch[y][0]);
        if (ch[x][1] && ch[y][1]) np.emplace_back(ch[x][1], ch[y][1]);

      }
    }
  }
  std::cout << ans;
  return 0;
}