题解 CF1902F Trees and XOR Queries Again

https://codeforces.com/contest/1902/problem/F

题意#

有一棵 $n$ 个顶点的树, 每个节点有一个权 $a_i$ , 给定 $q$ 个查询, 每次查询给定 $x, y, k$ , 判断 $x$ 到 $y$ 的简单路径上的点权集合是否存在某个子集异或和为 $k$ . $2 \le n \le 2e5$ , $0\le a_i\le 2^{20} - 1$ , $1\le q\le 2e5$ , $1\le x, y\le n$ , $0\le k\le 2^{20} - 1$ .

一些直觉#

对于子集异或和的问题, 最好的方法就是使用线性基. 本题的问题在于: 如何维护出 $x$ 到 $y$ 的简单路径上的线性基? 我们会发现他等于 $x$ 到 $lca(x, y)$ 的线性基与 $y$ 到 $lca(x, y)$ 的线性基合并(合并的复杂度: $O(log^2 V)\approx 400$ ).

现在的问题在于, 我们很好维护 $x$ 到根的线性基, 但是如何维护 $x$ 到某个祖宗的线性基? 我们注意到线性基具有优先级这个概念, 越靠前的基越优先, 于是, 我们每次维护线性基的时候, 如果出现两个基都能当做某一位的主元, 那么让深度更大的基当做主元即可, 深度小的基往下消元. 这样, 深度大的基一定更靠前. 所以每次如果 $lca(x, y)$ 的深度是 $d$ , 我们只需要用线性基中深度大于 $d$ 的基去消 $k$ , 本题也就解决了.

解题过程#

读入, 预处理
从根开始计算每个节点到根的简单路径上的线性基, 同时维护每个基对应的深度.
对于每个查询, 先算出 $x$ 到根的线性基与 $y$ 到根线性基合并的结果. 然后用合并后的线性基中深度大于等于 $lca(x, y)$ 的基去判断能否组成 $k$ 即可.

AC代码#

提交记录

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
using i128 = __int128;
5
using ull = unsigned long long;
6
using u32 = unsigned;
7
using u64 = unsigned long long;
8
using u128 = __uint128_t;
9
constexpr int INF = 0x3f3f3f3f;
10
constexpr ll INFLL = 2e18;
11

12
/* const */
13
constexpr double EPS = 1e-8;
14
constexpr ll MOD = 998244353;
15
constexpr int N = 1e6 + 50;
16

17
/* struct */
18

19
/* variable */
20

21
/* function */
22

23
void preprocess() {}
24
void solution() {
25
    /* code here */
26
    int n;
27
    cin >> n;
28
    vector<int> arr(n);
29
    for (int i = 0; i < n; i++) {
30
        cin >> arr[i];
31
    }
32
    vector adj(n, vector<int>());
33
    for (int i = 0; i < n - 1; i++) {
34
        int u, v;
35
        cin >> u >> v;
36
        u--, v--;
37
        adj[u].emplace_back(v);
38
        adj[v].emplace_back(u);
39
    }
40
    vector<array<int, 22>> up(n);
41
    queue<int> q;
42
    q.emplace(0);
43
    vector<int> ord;
44
    vector<int> vis(n);
45
    vector<int> d(n);
46
    up[0][0] = 0;
47
    d[0] = 0;
48
    vis[0] = 1;
49
    while (!q.empty()) {
50
        auto x = q.front();
51
        q.pop();
52
        ord.emplace_back(x);
53
        for (const auto& y : adj[x]) {
54
            if (!vis[y]) {
55
                q.emplace(y);
56
                vis[y] = 1;
57
                up[y][0] = x;
58
                d[y] = d[x] + 1;
59
            }
60
        }
61
    }
62
    for (int j = 1; j <= 20; j++) {
63
        for (int i = 0; i < n; i++) {
64
            up[i][j] = up[up[i][j - 1]][j - 1];
65
        }
66
    }
67
    auto lca = [&](ll a, ll b) -> ll {
68
        if (d[a] < d[b]) {
69
            swap(a, b);
70
        }
71
        for (int i = 20; i >= 0; i--) {
72
            if (d[up[a][i]] >= d[b]) {
73
                a = up[a][i];
74
            }
75
        }
76
        for (int i = 20; i >= 0; i--) {
77
            if (up[a][i] != up[b][i]) {
78
                a = up[a][i], b = up[b][i];
79
            }
80
        }
81
        if (a != b) {
82
            a = up[a][0], b = up[b][0];
83
        }
84
        return a;
85
    };
86
    struct item {
87
        int b = 0;
88
        int d = 0;
89
    };
90
    using Base = array<item, 20>;
91
    vector<array<item, 20>> base(n);
92
    auto insert = [&](item t, Base& a) -> bool {
93
        for (int i = 19; i >= 0; i--) {
94
            if (t.b >> i & 1) {
95
                if (a[i].b) {
96
                    if (t.d > a[i].d) {
97
                        swap(t.b, a[i].b);
98
                        swap(t.d, a[i].d);
99
                    }
100
                    t.b ^= a[i].b;
101
                } else {
102
                    a[i] = t;
103
                    return true;
104
                }
105
            }
106
        }
107
        return false;
108
    };
109
    for (int i = 0; i < n; i++) {
110
        int v = ord[i];
111
        base[v] = base[up[v][0]];
112
        insert({ arr[v], d[v] }, base[v]);
113
    }
114

115

116
    auto join = [&](const Base& a, Base& b) {
117
        for (int i = 19; i >= 0; i--) {
118
            if (a[i].b) {
119
                insert(a[i], b);
120
            }
121
        }
122
    };
123
    int sq;
124
    cin >> sq;
125
    for (int i = 0; i < sq; i++) {
126
        ll u, v, k;
127
        cin >> u >> v >> k;
128
        u--, v--;
129
        Base b{};
130
        join(base[u], b);
131
        join(base[v], b);
132
        bool flag = 1;
133
        int now = d[lca(u, v)];
134
        for (int j = 19; j >= 0; j--) {
135
            if (k >> j & 1) {
136
                if (b[j].b && b[j].d >= now) {
137
                    k ^= b[j].b;
138
                } else {
139
                    cout << "NO\n";
140
                    flag = 0;
141
                    break;
142
                }
143
            }
144
        }
145
        if (flag) {
146
            cout << "YES\n";
147
        }
148
    }
149
}
150
int main() {
151
    ios::sync_with_stdio(0), cin.tie(0);
152
    int t = 1;
153
    // cin >> t;
154
    preprocess();
155
    for (int i = 1; i <= t; i++) {
156
        solution();
157
    }
158
}
159
/* by ykindred */