# HE Dexter's Random Generator ( LCA, Persistent, Trie, XOR or Mo's ( TLE ) )

Dexter's Random Generator | Trie (Keyword Tree) & Data Structures Practice Problems | HackerEarth

1 ≤ N, Q ≤ 1e5
1 ≤ A[ i ] ≤ 1e9

O( N lg A + Q lg A )

```// Mo's TLE, score: 93
#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e5 );
const int MAXQ = int( 1e5 );

int N, Q;
int A[ MAXN ];
vector< int > G[ MAXN ];

int dpt[ MAXN ];
int par[ MAXN ][ 20 ];
void dfs_dpt( int u, int fa, int d ) {
dpt[ u ] = d + 1;
par[ u ][ 0 ] = fa;
for( int v : G[ u ] ) {
if( v == fa ) continue;
dfs_dpt( v, u, d + 1 );
}
}
int lca( int u, int v ) {
if( not ( dpt[ u ] >= dpt[ v ] ) ) {
swap( u, v );
}
int diff = dpt[ u ] - dpt[ v ];
for( int i = 20 - 1; diff; --i ) {
if( diff >= 1 << i ) {
diff -= 1 << i;
u = par[ u ][ i ];
}
}
if( u == v ) return u;
for( int i = 20 - 1; par[ u ][ 0 ] != par[ v ][ 0 ]; --i ) {
if( par[ u ][ i ] != par[ v ][ i ] ) {
u = par[ u ][ i ];
v = par[ v ][ i ];
}
}
return par[ u ][ 0 ];
}

int st[ MAXN ], ed[ MAXN ];
int flat[ MAXN * 2 ];
void dfs_flat( int u, int fa ) {
static int ts = 0;
st[ u ] = ts;
flat[ ts++ ] = u;
for( int v : G[ u ] ) {
if( v == fa ) continue;
dfs_flat( v, u );
}
ed[ u ] = ts;
flat[ ts++ ] = u;
}

struct trie {
trie *ch[ 2 ];
int cnt[ 2 ];
trie() {
ch[ 0 ] = ch[ 1 ] = NULL;
cnt[ 0 ] = cnt[ 1 ] = 0;
}
};

void add( trie *root, int x, int v, int t = 30 ) {
if( t == -1 ) return;
int k = x >> t & 1;
if( root->ch[ k ] == NULL ) {
root->ch[ k ] = new trie();
}
root->cnt[ k ] += v;
add( root->ch[ k ], x, v, t - 1 );
}

int get_max( trie *root, int x, int t = 30 ) {
if( t == -1 ) return 0;
int k = x >> t & 1;
if( root->ch[ k ^ 1 ] and root->cnt[ k ^ 1 ] ) {
return ( 1 << t ) + get_max( root->ch[ k ^ 1 ], x, t - 1 );
}
return get_max( root->ch[ k ], x, t - 1 );
}

int ans[ MAXQ ];
vector< tuple< int, int, int, int > > qry;

void print( trie *root, int v = 0, int t = 30 ) {
if( t < 0 ) {
cout << v << endl;
return;
}
if( root->ch[ 0 ] and root->cnt[ 0 ] ) {
print( root->ch[ 0 ], v, t - 1 );
}
if( root->ch[ 1 ] and root->cnt[ 1 ] ) {
print( root->ch[ 1 ], ( 1 << t ) + v, t - 1 );
}
}

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> Q;
for( int i = 0; i < N; ++i ) {
cin >> A[ i ];
}
for( int i = 0; i < N - 1; ++i ) {
int u, v;
cin >> u >> v;
--u, --v;
G[ u ].emplace_back( v );
G[ v ].emplace_back( u );
}
dfs_dpt( 0, -1, 0 );
for( int j = 0; j + 1 < 20; ++j ) {
for( int i = 0; i < N; ++i ) {
int m = par[ i ][ j ];
if( m == -1 ) continue;
par[ i ][ j + 1 ] = par[ m ][ j ];
}
}
dfs_flat( 0, -1 );
for( int qi = 0; qi < Q; ++qi ) {
int u, v;
cin >> u >> v;
--u, --v;
if( not ( st[ u ] <= st[ v ] ) ) {
swap( u, v );
}
int p = lca( u, v );
if( p == u ) {
qry.emplace_back( A[ u ], st[ u ], st[ v ], qi );
qry.emplace_back( A[ v ], st[ u ], st[ v ], qi );
} else {
ans[ qi ] = max( A[ u ] ^ A[ p ], A[ v ] ^ A[ p ] );
qry.emplace_back( A[ u ], ed[ u ], st[ v ], qi );
qry.emplace_back( A[ v ], ed[ u ], st[ v ], qi );
}
}
const int MAGIC = 300;
sort( qry.begin(), qry.end(), [ & ]( tuple< int, int, int, int > i, tuple< int, int, int, int > j ) {
if( get< 1 >( i ) / MAGIC != get< 1 >( j ) / MAGIC )
return get< 1 >( i ) / MAGIC < get< 1 >( j ) / MAGIC;
return get< 2 >( i ) < get< 2 >( j );
} );
for( int i = 0, lb = 1, rb = 0; i < qry.size(); ++i ) {
static trie *root = new trie();
static int vis[ MAXN * 2 ];
int x, ql, qr, id;
tie( x, ql, qr, id ) = qry[ i ];
while( lb < ql ) {
add( root, A[ flat[ lb ] ], ( ++vis[ flat[ lb ] ] & 1 ) ? 1 : -1 );
++lb;
}
while( ql < lb ) {
--lb;
add( root, A[ flat[ lb ] ], ( ++vis[ flat[ lb ] ] & 1 ) ? 1 : -1 );
}
while( rb < qr ) {
++rb;
add( root, A[ flat[ rb ] ], ( ++vis[ flat[ rb ] ] & 1 ) ? 1 : -1 );
}
while( qr < rb ) {
add( root, A[ flat[ rb ] ], ( ++vis[ flat[ rb ] ] & 1 ) ? 1 : -1 );
--rb;
}
ans[ id ] = max( ans[ id ], get_max( root, x ) );
}
for( int i = 0; i < Q; ++i ) {
cout << ans[ i ] << "\n";
}
return 0;
}
```

_

```// Persistent Trie
#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e5 );
const int MAXQ = int( 1e5 );

int N, Q;
int A[ MAXN ];
vector< int > G[ MAXN ];

int dpt[ MAXN ];
int par[ MAXN ][ 20 ];
void dfs_dpt( int u, int fa, int d ) {
dpt[ u ] = d + 1;
par[ u ][ 0 ] = fa;
for( int v : G[ u ] ) {
if( v == fa ) continue;
dfs_dpt( v, u, d + 1 );
}
}
int lca( int u, int v ) {
if( not ( dpt[ u ] >= dpt[ v ] ) ) {
swap( u, v );
}
int diff = dpt[ u ] - dpt[ v ];
for( int i = 20 - 1; diff; --i ) {
if( diff >= 1 << i ) {
diff -= 1 << i;
u = par[ u ][ i ];
}
}
if( u == v ) return u;
for( int i = 20 - 1; par[ u ][ 0 ] != par[ v ][ 0 ]; --i ) {
if( par[ u ][ i ] != par[ v ][ i ] ) {
u = par[ u ][ i ];
v = par[ v ][ i ];
}
}
return par[ u ][ 0 ];
}

struct trie {
trie *ch[ 2 ];
int cnt[ 2 ];
trie() {
ch[ 0 ] = ch[ 1 ] = NULL;
cnt[ 0 ] = cnt[ 1 ] = 0;
}
} *troot[ MAXN ];

trie* clone( trie *t ) {
trie *res = new trie();
if( not t ) return res;
for( int i = 0; i < 2; ++i ) {
res->ch[ i ] = t->ch[ i ];
res->cnt[ i ] = t->cnt[ i ];
}
return res;
}

trie* add( trie *root, int x, int v, int t = 30 ) {
if( t == -1 ) return NULL;
int k = x >> t & 1;
trie *res = clone( root );
if( res->ch[ k ] == NULL ) {
res->ch[ k ] = new trie();
}
res->cnt[ k ] += v;
res->ch[ k ] = add( root ? root->ch[ k ] : NULL, x, v, t - 1 );
return res;
}

int get_max( int x, trie *a, trie *b, trie *c, trie *d, int t ) { // a + b - c - d
if( t == -1 ) return 0;
int k = x >> t & 1;
int cnt = ( a ? a->cnt[ k ^ 1 ] : 0 ) + ( b ? b->cnt[ k ^ 1 ] : 0 ) - ( c ? c->cnt[ k ^ 1 ] : 0 ) - ( d ? d->cnt[ k ^ 1 ] : 0 );
if( cnt ) {
return ( 1 << t ) + get_max( x, ( a ? a->ch[ k ^ 1 ] : NULL ), ( b ? b->ch[ k ^ 1 ] : NULL ), ( c ? c->ch[ k ^ 1 ] : NULL ), ( d ? d->ch[ k ^ 1 ] : NULL ), t - 1 );
}
return get_max( x, ( a ? a->ch[ k ] : NULL ), ( b ? b->ch[ k ] : NULL ), ( c ? c->ch[ k ] : NULL ), ( d ? d->ch[ k ] : NULL ), t - 1 );
}

void dfs_construct_trie( int u, int fa, trie *p ) {
troot[ u ] = add( p, A[ u ], 1 );
for( int v : G[ u ] ) {
if( v == fa ) continue;
dfs_construct_trie( v, u, troot[ u ] );
}
}

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> Q;
for( int i = 0; i < N; ++i ) {
cin >> A[ i ];
}
for( int i = 0; i < N - 1; ++i ) {
int u, v;
cin >> u >> v;
--u, --v;
G[ u ].emplace_back( v );
G[ v ].emplace_back( u );
}
dfs_dpt( 0, -1, 0 );
for( int j = 0; j + 1 < 20; ++j ) {
for( int i = 0; i < N; ++i ) {
int m = par[ i ][ j ];
if( m == -1 ) continue;
par[ i ][ j + 1 ] = par[ m ][ j ];
}
}
dfs_construct_trie( 0, -1, NULL );
for( int qi = 0; qi < Q; ++qi ) {
int u, v;
cin >> u >> v;
--u, --v;
int p = lca( u, v );
if( p == v ) {
cout << max( { A[ u ] ^ A[ v ], get_max( A[ u ], troot[ u ], NULL, troot[ v ], NULL, 30 ), get_max( A[ v ], troot[ u ], NULL, troot[ v ], NULL, 30 ) } ) << "\n";
} else if( p == u ) {
cout << max( { A[ u ] ^ A[ v ], get_max( A[ u ], troot[ v ], NULL, troot[ u ], NULL, 30 ), get_max( A[ v ], troot[ v ], NULL, troot[ u ], NULL, 30 ) } ) << "\n";
} else {
cout << max( { A[ u ] ^ A[ p ], A[ v ] ^ A[ p ], get_max( A[ u ], troot[ u ], troot[ v ], troot[ p ], troot[ p ], 30 ), get_max( A[ v ], troot[ u ], troot[ v ], troot[ p ], troot[ p ], 30 ) } ) << "\n";
}
}
return 0;
}
```