fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(2e5)+7;
  14. const int LOG = 30;
  15.  
  16. int n , a[maxN] , d[maxN] , p[maxN] , sz[maxN];
  17. vector<int> g[maxN];
  18.  
  19. void dfs_init(int u){
  20.     d[u] = d[p[u]] ^ a[u];
  21.     sz[u] = 1;
  22.     for (int v : g[u]){
  23.         dfs_init(v);
  24.         sz[u] += sz[v];
  25.     }
  26. }
  27.  
  28. struct node{
  29.     int nxt[2] , cnt;
  30.  
  31.     node(){
  32.         cnt = 0;
  33.         nxt[0] = nxt[1] = -1;
  34.     }
  35. };
  36.  
  37. vector<node> trie;
  38.  
  39. int nxt_id(int id , int c){
  40.     if (id == -1) return -1; else return trie[id].nxt[c];
  41. }
  42.  
  43. int get_cnt(int id){
  44.     if (id == -1) return 0; else return trie[id].cnt;
  45. }
  46.  
  47. void update(int x , int y){
  48.     int id = 0;
  49.     for (int i = LOG ; i >= 0 ; i--){
  50.         int c = (x>>i)&1;
  51.         if (trie[id].nxt[c] == -1){
  52.             trie.push_back(node());
  53.             trie[id].nxt[c] = sz(trie) - 1;
  54.         }
  55.         id = trie[id].nxt[c];
  56.         trie[id].cnt += y;
  57.     }
  58. }
  59.  
  60. int get(int x){
  61.     int id = 0 , ans = 0;
  62.     if (get_cnt(nxt_id(id , 0)) + get_cnt(nxt_id(id , 1)) == 0) return 0;
  63.     for (int i = LOG ; i >= 0 ; i--){
  64.         int c = 1 - ((x>>i)&1);
  65.         if (get_cnt(nxt_id(id , c)) == 0){
  66.             c ^= 1;
  67.         }
  68.         else{
  69.             ans ^= (1<<i);
  70.         }
  71.         id = nxt_id(id , c);
  72.     }
  73.     return ans;
  74. }
  75.  
  76. int dp[maxN];
  77.  
  78. void dfs_update(int u , int x){
  79.     update(d[u] , x);
  80.     for (int v : g[u]){
  81.         dfs_update(v , x);
  82.     }
  83. }
  84.  
  85. void dfs_get(int u , int x){
  86.     dp[x] = max(dp[x] , get(d[u] ^ a[x]));
  87.     for (int v : g[u]){
  88.         dfs_get(v , x);
  89.     }
  90. }
  91.  
  92. void dfs_solve(int u){
  93.     dp[u] = a[u];
  94.     int heavy = -1;
  95.     for (int v : g[u]){
  96.         if (heavy == -1 || sz[heavy] < sz[v]) heavy = v;
  97.     }
  98.     for (int v : g[u]){
  99.         if (v != heavy){
  100.             dfs_solve(v);
  101.             dfs_update(v , -1);
  102.         }
  103.     }
  104.     if (heavy != -1) dfs_solve(heavy);
  105.     for (int v : g[u]){
  106.         if (v != heavy){
  107.             dfs_get(v , u);
  108.             dfs_update(v , +1);
  109.         }
  110.     }
  111.     dp[u] = max(dp[u] , get(d[u] ^ a[u]));
  112.     update(d[u] , +1);
  113.     for (int v : g[u]){
  114.         dp[u] = max(dp[u] , dp[v]);
  115.     }
  116. }
  117.  
  118. void solve(){
  119.     cin >> n;
  120.     trie.push_back(node());
  121.     for (int i = 1 ; i <= n ; i++){
  122.         cin >> a[i];
  123.     }
  124.     for (int i = 2 ; i <= n ; i++){
  125.         cin >> p[i];
  126.         g[p[i]].push_back(i);
  127.     }
  128.     dfs_init(1);
  129.     for (int i = 1 ; i <= n ; i++) update(d[i] , 0);
  130.     dfs_solve(1);
  131.     for (int i = 1 ; i <= n ; i++) cout << dp[i] << "\n";
  132. }
  133.  
  134. #define name "H"
  135.  
  136. int main(){
  137.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  138.     if (fopen(name".INP" , "r")){
  139.         freopen(name".INP" , "r" , stdin);
  140.         freopen(name".OUT" , "w" , stdout);
  141.     }
  142.     int t = 1; //cin >> t;
  143.     while (t--) solve();
  144.     return 0;
  145. }
  146.  
  147.  
Success #stdin #stdout 0.01s 10416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cHSNdR
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!