DDOSvoid's Blog

CF 1055F Tree and XOR

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/1055/F

简要题解：给定一棵 $n$ 个点有点权的无根树，求 $n^2$ 个路径中第 $k$ 小的路径异或和

$n\le 10^6$

Solution

找两两异或值的前 $k$ 小类似于在权值线段树上二分

由于爆空间，所以这题只能滚动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#define maxn 1000010
#define ll long long
using namespace std;

int n, a[maxn], b[maxn];

ll k, w[maxn];

struct Trie {
    int ch[2], v;
    void clear() { ch[0] = ch[1] = v = 0; } 
} T[maxn * 2]; int top = 1, rt = 1; 

ll ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k;
    for (int i = 2; i <= n; ++i) {
        int x; ll y; cin >> x >> y;
        w[i] = w[x] ^ y; 
    }
    for (int i = 1; i <= n; ++i) a[i] = b[i] = rt;
    for (int o = 61; ~o; --o) {
        top = o & 1 ? 1 : n + 1; 
        for (int i = 1; i <= n; ++i) {
            int &p = a[i], d = w[i] >> o & 1;
            if (!T[p].ch[d]) {
                T[++top].clear();
                T[p].ch[d] = top; 
            }
            ++T[p = T[p].ch[d]].v;
        } ll s = 0; 
        for (int i = 1; i <= n; ++i) {
            int p = b[i], d = w[i] >> o & 1;
            s += T[T[p].ch[d]].v;
        } int v = 0;
        if (k > s) k -= s, ans |= 1ll << o, v = 1;
        for (int i = 1; i <= n; ++i) {
            int &p = b[i], d = w[i] >> o & 1;
            p = T[p].ch[d ^ v]; 
        } 
    } cout << ans << endl; 
    return 0;
}