P8511 [Ynoi Easy Round 2021] TEST_68 题解

· · 题解

题解

异或最大，容易想到用 01 trie 来维护。

树上的一条链是容易维护的，我们令集合 S_x 表示 x 节点子树内的所有点，T_x 表示 x 节点子树外的所有点。

假设链上有两不同点 x,y 且 x 是 y 的祖先，那么一定有 S_x\in S_y，所以 T_y\in T_x，因此我们可以对链从上往下 dfs，把所有子树外且不在 trie 中的节点权值插入 trie 中，从而动态统计答案。

观察样例，发现有很多点的答案都是整棵树中最大的异或和。

我们设任意一组构成整棵树中最大的异或和的点对为 (x,y)，那么所有不在 x\to 1 这条链上且不在 y \to 1 这条链上的节点都能以 a_x\oplus a_y (即整棵树中最大的异或和) 作为答案。

那么我们就可以先求一遍整棵树最大的异或和并找到对应的 (x,y)，然后再求出 x\to 1 和 y\to 1 的答案，这样就做完了。

时间复杂度 O(n\log A)，空间复杂度 O(n\log A)。

当然可以也用压缩 trie 将空间复杂度降为 O(n)。

code：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int N = 5e5;

class trie {
private:
    int cnt;
    int val[N * 60], tr[N * 60][2];
public:
    void clear() {
        cnt = 0;
        memset(val, 0, sizeof(val));
        memset(tr, 0, sizeof(tr));
    }
    void ins(ll num, int id) {
        int x = 0;
        for (int i = 59; i >= 0; --i) {
            int v = (num >> i) & 1ll;
            if (!tr[x][v]) tr[x][v] = ++cnt;
            x = tr[x][v];
        }
        val[x] = id;
    }
    pair <ll, int> query(ll num) {
        int x = 0;
        ll res = 0;
        for (int i = 59; i >= 0; --i) {
            int v = (num >> i) & 1ll;
            if (!tr[x][v ^ 1]) x = tr[x][v];
            else x = tr[x][v ^ 1], res += 1ll << i;
        }
        return {res, val[x]};
    }
}T;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<int> fa(n + 1);
    vector<ll> a(n + 1);
    vector<vector<int>> G(n + 1);
    for (int i = 2; i <= n; ++i){
        int x;
        cin >> x;
        G[fa[i] = x].emplace_back(i);
    }
    pair <ll, pair<int, int>> ans;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        T.ins(a[i], i);
        auto t = T.query(a[i]);
        if (t.first > ans.first)
            ans = {t.first, {t.second, i}};
    }
    T.clear();
    vector<int> p, vis(n + 1), v(n + 1);
    vector<ll> Ans(n + 1);
    ll res = 0;
    for (int x = ans.second.first; x != 1; x = fa[x])
        p.emplace_back(x);
    reverse(p.begin(), p.end());
    v[1] = 1;
    auto dfs = [&](auto dfs, int x) -> void {
        T.ins(a[x], x);
        res = max(res, T.query(a[x]).first);
        for (auto y : G[x]) {
            if (vis[y]) continue;
            vis[y] = 1;
            dfs(dfs, y);
        }
    };
    for (int x : p) {
        vis[x] = v[x] = 1;
        dfs(dfs, fa[x]);
        Ans[x] = res;
    }
    T.clear();
    p.clear();
    res = 0;
    for (int &x : vis) x = 0;
    for (int x = ans.second.second; x != 1; x = fa[x])
        p.emplace_back(x);
    reverse(p.begin(), p.end());
    for (int x : p) {
        vis[x] = v[x] = 1;
        dfs(dfs, fa[x]);
        Ans[x] = res;
    }
    for (int i = 1; i <= n; ++i)
        if (v[i]) cout << Ans[i] << '\n';
        else cout << ans.first << '\n';
}