P8511 [Ynoi Easy Round 2021] TEST_68 题解

发表于 分类于 本文字数： 702 阅读时长 ≈ 2 分钟

true
TEST_68
Ynoi Easy Round 2021
省选/NOI-
#9d3dcf
  • Luogu P8511

题目要求我们对于每一个点，在其以1为根的子树外找到两个可以相同的点，使得其点权异或和最大。

首先我们需要知道怎么在一堆数里面找到异或和最大的一对。

我们考虑使用01Trie，边插入边查询，这样还可以动态维护，时间复杂度是单次修改或查询均为 $O(\log v)$，其中 $v$ 是值域。

为了方便，我这里的查询返回的是在序列中的下标。

Trie的代码如下：

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
struct Trie
{
    struct Node
    {
        int s[2];
        int end;
    };
    Node tr[N * 60];
    int idx;
    void clear()
    {
        for(int i = 0; i <= idx; i++)
            tr[i].s[0] = tr[i].s[1] = tr[i].end = 0;
        idx = 0;
    }
    void insert(ll x, int id)
    {
        int p = 0;
        for(int i = 59; i >= 0; i--)
        {
            int c = (x >> i) & 1;
            if(!tr[p].s[c])tr[p].s[c] = ++idx;
            p = tr[p].s[c];
        }
        tr[p].end = id;
    }
    int query(ll x)
    {
        int p = 0;
        for(int i = 59; i >= 0; i--)
        {
            int c = (x >> i) & 1;
            if(tr[p].s[c ^ 1])p = tr[p].s[c ^ 1];
            else if(tr[p].s[c])p = tr[p].s[c];
            else return 0;
        }
        return tr[p].end;
    }
};

有了快速查询的数据结构，我们就可以开始考虑如何快速求出答案了。

我们考虑利用支配的性质，先找到整棵树中点权异或和最大的两个点，设其为 $(x,y)$，考虑其对答案的贡献。

对于 $x$ 与 $y$ 都在子树外的点，其答案肯定就是 $a_x \oplus a_y$ 了。
这些点包括所有既不在 $x$ 到根的路径上又不在 $y$ 到根的路径上的点。

剩下的点我们需要手动求一遍其答案。
为了使我们的时间复杂度保持在一个较低的水平，我们需要将剩下的这些点拆成 1 到 $x$ 和 $\operatorname{lca}(x,y)$ 到 $y$ 这两条路径，并分别从上到下依次求出答案。
这样可以保证我们在进行这些操作的时候只会插入 $O(n)$ 个节点，因为一条链上的子树补从上到下依次被下层节点包含，大小最多不会超过 $O(n)$，维护这个东西只需要一直插入就好了。

求LCA不需要什么别的算法来辅助，我们直接暴力跳就好了，期间顺便标记上 $x$ 到 $y$ 路径上的点，反正最后还是需要遍历每一个点，这时候节省的时间可以忽略不计。

再配合上Trie的 $O(\log v)$ 复杂度，总时间复杂度就变成了 $O(n \log v)$。

代码如下：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 500010, M = N << 1;
struct Trie
{
    struct Node
    {
        int s[2];
        int end;
    };
    Node tr[N * 60];
    int idx;
    void clear()
    {
        for(int i = 0; i <= idx; i++)
            tr[i].s[0] = tr[i].s[1] = tr[i].end = 0;
        idx = 0;
    }
    void insert(ll x, int id)
    {
        int p = 0;
        for(int i = 59; i >= 0; i--)
        {
            int c = (x >> i) & 1;
            if(!tr[p].s[c])tr[p].s[c] = ++idx;
            p = tr[p].s[c];
        }
        tr[p].end = id;
    }
    int query(ll x)
    {
        int p = 0;
        for(int i = 59; i >= 0; i--)
        {
            int c = (x >> i) & 1;
            if(tr[p].s[c ^ 1])p = tr[p].s[c ^ 1];
            else if(tr[p].s[c])p = tr[p].s[c];
            else return 0;
        }
        return tr[p].end;
    }
};

int n;
int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
ll a[N], ans[N];
Trie tr;
int l1, l2; ll maxn;
int dep[N], fa[N];
bool tag[N];
void dfs1(int p, int fa)
{
    dep[p] = dep[fa] + 1, ::fa[p] = fa;
    for(int i = h[p]; ~i; i = ne[i])
    {
        if(e[i] == fa)continue;
        dfs1(e[i], p);
    }
}
int lca(int p, int q)
{
    if(dep[p] < dep[q])swap(p, q);
    tag[p] = tag[q] = true;
    while(dep[p] > dep[q])p = fa[p], tag[p] = true;
    if(p == q)return p;
    while(p != q)p = fa[p], q = fa[q], tag[p] = tag[q] = true;
    return p;
}
int sta[N], tt;
bool vis[N];
void dfs2(int p, int fa)
{
    tr.insert(a[p], p);
    int q = tr.query(a[p]);
    if((a[p] ^ a[q]) > maxn)maxn = a[p] ^ a[q];
    for(int i = h[p]; ~i; i = ne[i])
    {
        if(e[i] == fa || vis[e[i]])continue;
        dfs2(e[i], p);
    }
}
void solve(int p, int q)
{
    if(p == q)return;
    if(dep[p] < dep[q])swap(p, q);
    tt = 0;
    while(p != q)sta[++tt] = p, vis[p] = true, p = fa[p];
    tr.clear(), maxn = 0;
    dfs2(1, 0);
    for(int i = tt; i; i--)
    {
        ans[sta[i]] = maxn;
        dfs2(sta[i], fa[sta[i]]);
        vis[sta[i]] = false;
    }
}
int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d", &n);
    for(int i = 2; i <= n; i++)
    {
        int fa;
        scanf("%d", &fa);
        add(i, fa), add(fa, i);
    }
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    tr.clear();
    for(int i = 1; i <= n; i++)
    {
        tr.insert(a[i], i);
        int j = tr.query(a[i]);
        if((a[i] ^ a[j]) > maxn)l1 = j, l2 = i, maxn = a[i] ^ a[j];
    }
    dfs1(1, 0);
    int g = lca(l1, l2);
    for(int i = g; i >= 1; i = fa[i])tag[i] = true;
    for(int i = 2; i <= n; i++)
        if(!tag[i])ans[i] = maxn;
    solve(1, l1);
    solve(g, l2);
    for(int i = 1; i <= n; i++)
        printf("%lld\n", ans[i]);
    return 0;
}