Query on A Tree(可持久化01字典树)

描述

传送门:HDU6191

Monkey A lives on a tree, he always plays on this tree.

One day, monkey A learned about one of the bit-operations, xor. He was keen of this interesting operation and wanted to practise it at once.

Monkey A gave a value to each node on the tree. And he was curious about a problem.

The problem is how large the xor result of number $x$ and one node value of label $y$ can be, when giving you a non-negative integer $x$ and a node label $u$ indicates that node $y$ is in the subtree whose root is $u$(y can be equal to $u$).

Can you help him?

Input

There are no more than $6$ test cases.

For each test case there are two positive integers $n$ and $q$, indicate that the tree has $n$ nodes and you need to answer $q$ queries.

Then two lines follow.
The first line contains $n$ non-negative integers $V_1,V_2,⋯,V_n$, indicating the value of node $i$.
The second line contains $n-1$ non-negative integers $F_1,F_2,…F_{n−1}$, $F_i$ means the father of node $i+1$.

And then $q$ lines follow.
In the $i$-th line, there are two integers $u$ and $x$, indicating that the node you pick should be in the subtree of $u$, and $x$ has been described in the problem.
$2≤n,q≤10 ^ 5$
$0≤V_i≤10 ^ 9$
$1≤F_i≤n$, the root of the tree is node $1$.
$1≤u≤n,0≤x≤10 ^ 9$

Output

For each query, just print an integer in a line indicating the largest result.

Sample Input

1
2
3
4
5
2 2
1 2
1
1 3
2 1

Sample Output

1
2
2
3

思路

  • 先在树上跑一遍dfs序转为线性结构,然后问题就转变为在一个区间内选择一个数$s$与$x$的异或值最大。
  • 用Trie来维护区间内每个数的每一位,然后在Trie上贪心查询即可(即尽量取和当前位不一样的值)
  • 但是要对付这么多查询,我们不能每次都建一个Trie,所以考虑用莫队离线。
  • 比较坑的地方就在于莫队中的删除操作,由于某个前缀(甚至某个数)可能出现多次,所以要在Trie中记录每个结点的访问次数,删除的时候仅减1!(因为这个错了好几次)
  • 这题也可以使用启发式合并,维护每个点的子树,把询问离线对应到树上每个点即可。(不会0.0)

过了好久来补可持久化字典树的做法。

  • 跑完dfs序后,按dfs序建可持久化字典树,维护dfs序前$x$个中每个数的出现次数,这样每次版本更新的时候只会更新(新增)$\log(v)$个结点,其他结点都可以继承上一个版本的信息。
  • 然后查询的时候只要sz[out[u]]-sz[in[u]-1]>0就说明可以走这个点,贪心即可。

代码

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <bits/stdc++.h>
using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

// Graph
const int maxn = 1e5 + 5;
vector <int> G[maxn];
int TL[maxn], TR[maxn], a[maxn], dfn;

void init(int n)
{
for (int i = 1; i <= n; i++)
G[i].clear();
dfn = 0;
}

void dfs(int u)
{
TL[u] = ++dfn;
for (auto& v : G[u])
dfs(v);
TR[u] = dfn;
}

// Trie
int ch[maxn * 32][2];
int val[maxn * 32];
int num[maxn * 32];
int sz;
void initTrie()
{
sz = 1;
clr(ch[0], 0);
clr(val, 0);
clr(num, 0);
}

void insert(const int x)
{
int u = 0;
for (int i = 31; i >= 0; i--)
{
int c = (x >> i) & 1;
if (!ch[u][c])
{
clr(ch[sz], 0);
ch[u][c] = sz++;
val[sz] = 0;
num[sz] = 0;
}
u = ch[u][c];
num[u]++;
}
val[u] = x;
}

int find(const int x)
{
int u = 0;
for (int i = 31; i >= 0; i--)
{
int c = (x >> i) & 1;
if (ch[u][c ^ 1] && num[ch[u][c ^ 1]])
c ^= 1;
u = ch[u][c];
}
return val[u];
}

void del(const int x)
{
int u = 0;
for (int i = 31; i >= 0; i--)
{
int c = (x >> i) & 1;
if (!ch[u][c])
return;
u = ch[u][c];
num[u]--;
}
}

// Mo
int q, ans[maxn];
double unit;

struct query
{
int L, R, X, id;
query() {}
query(int l, int r, int x, int i): L(l), R(r), X(x), id(i) {}
} node[maxn];

bool cmp(query a, query b)
{
if (a.L / unit != b.L / unit)
return a.L / unit < b.L / unit;
else
return a.R < b.R;
}

void solve()
{
initTrie();
int tmp;
int L = 1;
int R = 0;
for (int i = 0; i < q; i++)
{
while (node[i].L < L) insert(a[--L]);
while (node[i].L > L) del(a[L++]);
while (node[i].R < R) del(a[R--]);
while (node[i].R > R) insert(a[++R]);
tmp = find(node[i].X);
ans[node[i].id] = tmp ^ node[i].X;
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n;
while (~scanf("%d%d", &n, &q))
{
init(n);
int t[maxn];
for (int i = 1; i <= n; i++)
scanf("%d", t + i);
for (int i = 2; i <= n; i++)
{
int tmp;
scanf("%d", &tmp);
G[tmp].pb(i);
}
dfs(1);
for (int i = 1; i <= n; i++)
a[TL[i]] = t[i];
unit = sqrt(n);
for (int i = 0; i < q; i++)
{
int u, x;
scanf("%d%d", &u, &x);
node[i] = query(TL[u], TR[u], x, i);
}
sort(node, node + q, cmp);
solve();
for (int i = 0; i < q; i++)
printf("%d\n", ans[i]);
}
return 0;
}
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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int N = 1 << 17;
struct Trie
{
int sz[N << 5], ch[N << 5][2], tot;
int rt[N];
void init()
{
tot = 0;
clr(rt, 0);
rt[0] = newNode();
}
int newNode()
{
clr(ch[tot], 0);
sz[tot] = 0;
return tot++;
}
void insert(int val, int x, int y)
{
rt[x] = newNode();
int u = rt[x], v = rt[y];
for (int i = 30; ~i; i--)
{
int d = val >> i & 1;
sz[u] = sz[v] + 1;
ch[u][d] = newNode();
ch[u][d ^ 1] = ch[v][d ^ 1];
u = ch[u][d], v = ch[v][d];
}
sz[u] = sz[v] + 1;
}
int query(int val, int x, int y)
{
int u = rt[x], v = rt[y];
int ans = 0;
for (int i = 30; ~i; i--)
{
int d = val >> i & 1;
int t = sz[ch[v][d ^ 1]] - sz[ch[u][d ^ 1]];
if (t > 0) d ^= 1;
ans |= d << i;
u = ch[u][d], v = ch[v][d];
}
return ans;
}
} trie;

int val[N];
vector<int> G[N];
int in[N], out[N], dfn;

void dfs(int u)
{
trie.insert(val[u], dfn + 1, dfn);
in[u] = ++dfn;
for (auto& v : G[u]) dfs(v);
out[u] = dfn;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, q;
while (~scanf("%d%d", &n, &q))
{
trie.init(), dfn = 0;
for (int i = 1; i <= n; i++)
{
G[i].clear();
scanf("%d", val + i);
}
for (int i = 2, v; i <= n; i++)
{
scanf("%d", &v);
G[v].push_back(i);
}
dfs(1);
while (q--)
{
static int u, x;
scanf("%d%d", &u, &x);
printf("%d\n", x ^ trie.query(x, in[u] - 1, out[u]));
}
}
return 0;
}
捐助作者