fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  6.  
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. using namespace __gnu_pbds;
  10.  
  11. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set;
  12. typedef pair<int, int>pr;
  13. #define all(i)     i.begin() , i.end()
  14. #define ft     first
  15. #define sn     second
  16. #define pb     push_back
  17. #define totalone(mask)  __builtin_popcount(mask)
  18. #define chkbit(mask,bit)  (mask&(1LL << bit))
  19.  
  20. // debug section start
  21. void __print(int x) {cerr << x;}
  22. void __print(long x) {cerr << x;}
  23. void __print(long long x) {cerr << x;}
  24. void __print(unsigned x) {cerr << x;}
  25. void __print(unsigned long x) {cerr << x;}
  26. void __print(unsigned long long x) {cerr << x;}
  27. void __print(float x) {cerr << x;}
  28. void __print(double x) {cerr << x;}
  29. void __print(long double x) {cerr << x;}
  30. void __print(char x) {cerr << '\'' << x << '\'';}
  31. void __print(const char *x) {cerr << '\"' << x << '\"';}
  32. void __print(const string &x) {cerr << '\"' << x << '\"';}
  33. void __print(bool x) {cerr << (x ? "true" : "false");}
  34.  
  35. template<typename T, typename V>
  36. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  37. template<typename T>
  38. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  39. void _print() {cerr << "]\n";}
  40. template <typename T, typename... V>
  41. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  42. #ifndef ONLINE_JUDGE
  43. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  44. #else
  45. #define debug(x...)
  46. #endif
  47. // debug section closed
  48.  
  49. #define en "\n"
  50. #define sum(n) ((1LL*(n)*(n+1))/ 2LL)
  51. #define sqr(n) (1LL*(n)*(n))
  52. #define vag(a,b) ((a + b - 1)/b)
  53.  
  54. #define MAXN 500005
  55. #define inf 1e6+5
  56. const int mod = 1e9 + 7;
  57.  
  58. ll n;
  59. ll a[MAXN], vis[MAXN];
  60. vector<ll>g[MAXN];
  61.  
  62. struct trie
  63. {
  64.     ll g[MAXN * 31][2];
  65.     ll cn[MAXN * 31][2];
  66.  
  67.     ll cur;
  68.     void init()
  69.     {
  70.         memset(g, -1, sizeof(g));
  71.         memset(cn, 0, sizeof(cn));
  72.         cur = 0;
  73.     }
  74.     void Insert(ll d)
  75.     {
  76.         ll nd = 0;
  77.         ll xr = 0;
  78.         for (ll i = 30; i >= 0; i--)
  79.         {
  80.             bool x = chkbit(d, i);
  81.             cn[nd][x]++;
  82.             if (g[nd][x] == -1) g[nd][x] = ++cur;
  83.             nd = g[nd][x];
  84.         }
  85.     }
  86.  
  87.     ll query(ll d)
  88.     {
  89.         ll nd = 0;
  90.         ll xr = 0;
  91.         for (ll i = 30; i >= 0; i--)
  92.         {
  93.             bool x = chkbit(d, i);
  94.             bool y = (1 ^ x);
  95.  
  96.             if (g[nd][y] != -1)
  97.             {
  98.                 xr |= (1LL << i);
  99.                 nd = g[nd][y];
  100.             }
  101.             else if (g[nd][x] != -1)
  102.             {
  103.                 nd = g[nd][x];
  104.             }
  105.             else break;
  106.         }
  107.         return xr;
  108.     }
  109.     void Erase(ll d)
  110.     {
  111.         ll nd = 0;
  112.         for (ll i = 30; i >= 0; i--)
  113.         {
  114.             bool x = chkbit(d, i);
  115.             cn[nd][x]--;
  116.             if (cn[nd][x] == 0)
  117.             {
  118.                 g[nd][x] = -1;
  119.                 break;
  120.             }
  121.             nd = g[nd][x];
  122.         }
  123.     }
  124.  
  125. } tri;
  126. ll an;
  127.  
  128. void dfs(ll nd)
  129. {
  130.     vis[nd] = 1;
  131.  
  132.     ll xr = tri.query(a[nd]);
  133.     an = max(an, xr);
  134.  
  135.     tri.Insert(a[nd]);
  136.  
  137.     for (auto i : g[nd])
  138.     {
  139.         if (vis[i]) continue;
  140.         dfs(i);
  141.     }
  142.     tri.Erase(a[nd]);
  143. }
  144. void solve()
  145. {
  146.     cin >> n;
  147.     for (ll i = 1; i <= n; i++) {
  148.         cin >> a[i];
  149.     }
  150.  
  151.     for (ll i = 1; i < n; i++) {
  152.         ll x, y;
  153.         cin >> x >> y;
  154.         g[x].pb(y);
  155.         g[y].pb(x);
  156.     }
  157.  
  158.     tri.init();
  159.     dfs(1);
  160.  
  161.     cout << an << en;
  162. }
  163. int main()
  164. {
  165.     IOS;
  166.     ll t;
  167.     t = 1;
  168.     // cin >> t;
  169.  
  170.     int c = 0;
  171.     while ( t-- )
  172.     {
  173.         // cout<<"Case "<<++c<<": ";
  174.         solve();
  175.     }
  176.     return 0;
  177. }
Success #stdin #stdout 0.2s 500692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/44UYkM
language:
C++14 (gcc 8.3)
created:
351 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!