PROBLEM LINK:
Practice
Contest, div. 1
Contest, div. 2
Author: Surya Prakash
Tester: Zhong Ziqian
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM
PREREQUISITES:
Persistent bit trie
PROBLEM:
You’re given rooted tree on N vertices. Each vertex has weight w_i. You should answer Q queries in online, in each query you’re given vertex v and parameter k. You have to find maximum possible w_u \oplus k where u is in subtree of v and has smallest possible number.
QUICK EXPLANATION:
In offline you would solve this problem with merging tries across tree using small-to-large trick. For online solution just add a bit of persistency.
EXPLANATION:
Problem “Given n numbers, find the one having largest xor with the current one” is well-known and is solvable with bit trie greedily. That is, in each vertex you first try to go to the one which will give 1 in considered bit and if it’s not possible, you go in another direction. Note that bitwise trie is efficiently representable as a segment tree. That is, let maxm=2^k where k is the largest possible bitwise length of numbers from input, then if mn[v] is vertex from initial tree with minimum number having weight in the segment of vertex v in segment tree, you may get an answer like this:
int L[maxs], R[maxs], mn[maxs];
pair<int, int> get(int k, int v, int l = 0, int r = maxm) {
if(r - l == 1) {
return {mn[v], l};
} else {
int m = (l + r) / 2;
if(((k ^ (m - l)) < k && L[v]) || !R[v]) {
return get(k, L[v], l, m);
} else {
return get(k, R[v], m, r);
}
}
}
Note that m-l here represents is the power of two, thus k \oplus (m-l) efficiently checks if corresponding bit is set to 1 in k.
Now how does it help us to solve the problem? If it was formulated in off-line manner, we may utilize the smaller-to-larger trick when you make a tour over the tree and when you’re in vertex v you compute the whole set of its descendants by merging sets of its children from smaller to larger. This will take O(n \log n) insertions overall because any vertex will change its set only O(\log n) times.
What to do with online queries? Utilize persistency, of course! We may make trees persistent so we may precalculate all sets and have a way to access any of them in the future. It works like this:
int w[maxn];
vector<int> g[maxn];
set<int> sub[maxn];
void dfs(int v = 1, int p = 1) {
rt[v] = copy();
sub[v] = {v};
upd(w[v], v, rt[v]);
for(auto u: g[v]) {
if(u != p) {
dfs(u, v);
if(sub[v].size() < sub[u].size()) {
rt[v] = copy(rt[u]);
swap(sub[v], sub[u]);
}
for(auto it: sub[u]) {
sub[v].insert(it);
upd(w[it], it, rt[v]);
}
}
}
}
Here we introduced two new function: copy just makes a copy of a vertex:
int copy(int v = 0) {
L[sz] = L[v];
R[sz] = R[v];
mn[sz] = mn[v];
return sz++;
}
And, finally, upd function is where you really use persistency to keep results:
void upd(int p, int c, int v, int l = 0, int r = maxm) {
mn[v] = min(mn[v], c);
if(r - l > 1) {
int m = (l + r) / 2;
if(p < m) {
upd(p, c, L[v] = copy(L[v]), l, m);
} else {
upd(p, c, R[v] = copy(R[v]), m, r);
}
}
}
After we implemented all these functions, whole solution is very simple:
int x = 0, y = 0;
while(q--) {
int k, v;
cin >> v >> k;
v ^= x, k ^= y;
tie(x, y) = get(k, rt[v]);
y ^= k;
cout << x << ' ' << y << "\n";
}
Don’t forget to wipe out all data between tests!
Challenge: Solve the problem with O(N \log NC) memory instead of O(N \log N \log C).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.