ulvis.paste.net

Paste Search Dynamic
Recent pastes
ans
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ull = uint64_t;
  4. using ll = int64_t;
  5. using ld = long double;
  6.  
  7. const int MAXN = 1000228;
  8. const int LG = 6;
  9.  
  10. ll f[MAXN];
  11.  
  12. int e[MAXN * 2][2];
  13. int p[MAXN];
  14. int q[MAXN];
  15.  
  16. int s[MAXN * 2];
  17.  
  18. const int ROOT = 1;
  19. const int B = 62;
  20.  
  21. int getbit(int i, int j) {
  22.     return (f[i] >> j) & 1;
  23. }
  24.  
  25. int main() {
  26. #ifdef BZ
  27.     freopen("input.txt", "r", stdin);
  28. #endif
  29.     ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(20);
  30.     int n;
  31.     cin >> n;
  32.     ll k;
  33.     cin >> k;
  34.  
  35.     for (int i = 1; i < n; ++i) {
  36.         int p;
  37.         ll w;
  38.         cin >> p >> w;
  39.         f[i] = f[p - 1] ^ w;
  40.     }
  41.  
  42.  
  43.     fill(p, p + n, 1);
  44.     fill(q, q + n, 1);
  45.  
  46.     ll ans = 0;
  47.  
  48.     for (int j = B - 1; j >= 0; --j) {
  49.         int nd = 2;
  50.         memset(s, 0, sizeof(s));
  51.         memset(e, 0, sizeof(e));
  52.  
  53.         for (int i = 0; i < n; ++i) {
  54.             int b = getbit(i, j);
  55.             if (e[q[i]][b] == 0) {
  56.                 e[q[i]][b] = nd++;
  57.             }
  58.  
  59.             q[i] = e[q[i]][b];
  60.             ++s[q[i]];
  61.         }
  62.  
  63.         ll c = 0;
  64.  
  65.         for (int i = 0; i < n; ++i) {
  66.             c += s[e[p[i]][getbit(i, j)]];
  67.         }
  68.  
  69.         int xr = 0;
  70.         if (c < k) {
  71.             xr = 1;
  72.             k -= c;
  73.             ans += (1ll << j);
  74.         }
  75.  
  76.         for (int i = 0; i < n; ++i) {
  77.             p[i] = e[p[i]][getbit(i, j) ^ xr];
  78.         }
  79.     }
  80.  
  81.     cout << ans << "\n";
  82. }
Parsed in 0.012 seconds