In this HackerEarth Dexter's Random Generator problem solution Dexter has recently constructed a random generator. This generator works on a tree of N nodes. The information about the tree has to be fed into the generator in order for it to start working.

Each node, u of the tree has a value A[u] associated with it. The generator works as follows:

It takes as input two integers, u and v. It then outputs two integers X and Y. X can be either A[u] or A[v], with equal probability. Now, the generator selects a node i randomly and with equal probability from the path u - v (including u and v) in the tree and outputs the value of Y as A[i].

Let the above process be denoted by: Process(u,v), which takes input a pair of integers and outputs a pair of integers (X, Y).

Now, Hannah has been invited to test the random generator constructed by Dexter. Hannah has Q questions. Each question is as follows:

Hannah selects two nodes u and v of the tree. She wants to know the maximum value of Query(u,v).


HackerEarth Dexter's Random Generator problem solution


HackerEarth Dexter's Random Generator problem solution.

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
const int LIM = 31;
const int LOGN = 20;
vector <int> g[N];

int a[N];
int trie[N * LIM] , to[N * LIM][2], ptr;
int root[N];

int insert(int num, int lev, int root) {
int newRoot = ++ptr;
int cur = newRoot;
for(int i = LIM-1 ; i >= 0 ; i --) {
int bit = (num >> i) & 1;
to[cur][bit^1] = to[root][bit^1];
to[cur][bit] = ++ptr;
root = to[root][bit];
cur = to[cur][bit];
trie[cur] = lev;
}
return newRoot;
}

int query(int num, int lev, int root) {
int cur = root;
int ret = 0;
for(int i = LIM-1 ; i >= 0 ; i --) {
int bit = (num >> i) & 1;
if(to[cur][bit ^ 1] && trie[to[cur][bit^1]] >= lev) {
ret = ret * 2 + 1;
cur = to[cur][bit ^ 1];
}
else {
ret = ret * 2;
cur = to[cur][bit];
}
}
return ret;
}

int level[N] , P[LOGN][N];

void dfs(int u , int p){
P[0][u] = p;
for(int i = 1 ; i < LOGN ; i ++)
P[i][u] = P[i-1][P[i-1][u]];
root[u] = insert(a[u], level[u], root[p]);
for(int i = 0 ; i < g[u].size();i++)
if(g[u][i] != p){
level[g[u][i]] = level[u] + 1;
dfs(g[u][i] , u);
}
}

inline int LCA(int x , int y){
if(level[x] < level[y])swap(x , y);
int lg = 1; for(;(1<<lg) <= level[x] ; lg ++);lg--;
for(int i = lg ; i >= 0 ; i--)
if(level[x] - (1<<i) >= level[y])
x = P[i][x];
if(x == y)return x;
for(int i = lg ; i >= 0 ; i--)
if(P[i][x] != -1 && P[i][x] != P[i][y]){
x = P[i][x];
y = P[i][y];
}
return P[0][x];
}

int main() {
ptr = 1;
int n,m; cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i < n; i ++) {
int u,v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
while(m --) {
int u,v; cin >> u >> v;
int lca = LCA(u,v);
int lev = level[lca];
int ans = query(a[u], lev, root[u]);
ans = max(ans, query(a[u], lev, root[v]));
ans = max(ans, query(a[v], lev, root[u]));
ans = max(ans, query(a[v], lev, root[v]));
cout << ans << endl;
}
return 0;
}