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

題意：
給一棵節點帶權的樹。每次詢問一條路徑，問路徑其中一個端點和路徑中任意節點的最大 XOR 值是多少。

制約：
1 ≤ N, Q ≤ 1e5
1 ≤ A[ i ] ≤ 1e9

解法：
第一種方法是用莫隊，將時間戳記做好，進去和出來的時候都塞進一個 vector，這麼一來，路徑可以用這個 vector 上的區間來描述。若一個元素在那區間裡出現兩次就無視它的影響，因為代表它不在路徑裡。這個做法 93 分。
第二種是用持久化 Trie。讓每一個節點都帶有一個持久化 Trie。具體來說，對於 u 的兒節點 v，root[ v ] = add( root[ u ], A[ v ] )。這麼一來，假如要求的是 u, v 路徑上的答案，那麼找到 p = lca( u, v )，( 為了方便假設 p != u and p != v ) 則 u, v 路徑上形成的 Trie 是 root[ u ] + root[ v ] - 2 * root[ p ] + A[ p ]。

時間 / 空間複雜度：
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;
}