Advertisement
esraa_syam

trie

Sep 2nd, 2024
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.78 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. #define nl "\n"
  5. #define ll long long
  6. #define mod  1'000'000'007
  7. #define all(v) v.begin(), v.end()
  8. #define rall(v) v.rbegin(), v.rend()
  9. #define sz(v) (int) v.size()
  10.  
  11. template<typename T = int>
  12. istream &operator>>(istream &in, vector<T> &v) {
  13.     for (auto &x: v) in >> x;
  14.     return in;
  15. }
  16.  
  17. template<typename T = int>
  18. ostream &operator<<(ostream &out, const vector<T> &v) {
  19.     for (const T &x: v) out << x << " ";
  20.     return out;
  21. }
  22.  
  23. void Sira() {
  24.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  25. #ifndef ONLINE_JUDGE
  26.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  27. #endif
  28. }
  29. struct BinaryTrie {
  30.     struct Node{
  31.         Node* child[2];
  32.         int freq[2];
  33.  
  34.         Node(){
  35.             child[0] = child[1] = 0;
  36.             freq[0] = freq[1] = 0;
  37.         }
  38.  
  39.     };
  40.  
  41.     Node* root = new Node();
  42.  
  43.     void insert(ll n){
  44.         Node* cur = root;
  45.  
  46.         for(ll i = 61 ; i >= 0 ; i--){
  47.             ll bit = (n >> i) & 1;
  48.  
  49.             if(!cur->child[bit]){
  50.                 cur->child[bit] = new Node();
  51.             }
  52.  
  53.             cur->freq[bit]++;
  54.             cur = cur->child[bit];
  55.         }
  56.     }
  57.  
  58.     void remove(ll n , ll i , Node* cur){
  59.         if(i < 0) return;
  60.  
  61.         ll bit = (n >> i) & 1;
  62.  
  63.         remove(n , i - 1 , cur->child[bit]);
  64.  
  65.         cur->freq[bit]--;
  66.  
  67.         if(!cur->freq[bit]){
  68.             delete cur->child[bit];
  69.             cur->child[bit] = 0;
  70.         }
  71.     }
  72.  
  73.     ll mn_xor(ll n){
  74.         Node* cur = root;
  75.         ll ans = 0;
  76.  
  77.         for(ll i = 61 ; i >= 0 ; i--){
  78.             ll bit = (n >> i) & 1;
  79.  
  80.             if(cur->child[bit]){
  81.                 cur = cur->child[bit];
  82.             }else{
  83.                 ans |= (1ll << i);
  84.                 cur = cur->child[bit ^ 1];
  85.             }
  86.         }
  87.  
  88.         return ans;
  89.     }
  90. };
  91.  
  92. void solve(){
  93.     BinaryTrie trie;
  94.  
  95.     int n;
  96.     cin >> n;
  97.  
  98.     vector < vector < ll > > adj(n + 5);
  99.  
  100.     for(int i = 2 ; i <= n ; i++){
  101.         int x;
  102.         cin >> x;
  103.         adj[x].push_back(i);
  104.     }
  105.  
  106.     vector < ll > pow(n + 1) , ans(n + 1);
  107.  
  108.     for(int i = 1 ; i <= n ; i++) cin >> pow[i];
  109.  
  110.     function < void(int) > dfs = [&](int src){
  111.         ans[src] = trie.mn_xor(pow[src]);
  112.         trie.insert(pow[src]);
  113.  
  114.         for(auto & nxt : adj[src]){
  115.             dfs(nxt);
  116.             ans[src] = min(ans[src] , ans[nxt]);
  117.         }
  118.         trie.remove(pow[src] , 61 , trie.root);
  119.     };
  120.  
  121.     trie.insert(-1);
  122.     dfs(1);
  123.  
  124.     int q;
  125.     cin >> q;
  126.  
  127.     while(q--){
  128.         int x;
  129.         cin >> x;
  130.         cout << ans[x] << nl;
  131.     }
  132. }
  133.  
  134. int main() {
  135.     Sira();
  136.     int t = 1;
  137. //    cin >> t;
  138.     while(t--){
  139.         solve();
  140.     }
  141.     return 0;
  142. }
  143.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement