Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- #define nl "\n"
- #define ll long long
- #define mod 1'000'000'007
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define sz(v) (int) v.size()
- template<typename T = int>
- istream &operator>>(istream &in, vector<T> &v) {
- for (auto &x: v) in >> x;
- return in;
- }
- template<typename T = int>
- ostream &operator<<(ostream &out, const vector<T> &v) {
- for (const T &x: v) out << x << " ";
- return out;
- }
- void Sira() {
- ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- #endif
- }
- struct BinaryTrie {
- struct Node{
- Node* child[2];
- int freq[2];
- Node(){
- child[0] = child[1] = 0;
- freq[0] = freq[1] = 0;
- }
- };
- Node* root = new Node();
- void insert(ll n){
- Node* cur = root;
- for(ll i = 61 ; i >= 0 ; i--){
- ll bit = (n >> i) & 1;
- if(!cur->child[bit]){
- cur->child[bit] = new Node();
- }
- cur->freq[bit]++;
- cur = cur->child[bit];
- }
- }
- void remove(ll n , ll i , Node* cur){
- if(i < 0) return;
- ll bit = (n >> i) & 1;
- remove(n , i - 1 , cur->child[bit]);
- cur->freq[bit]--;
- if(!cur->freq[bit]){
- delete cur->child[bit];
- cur->child[bit] = 0;
- }
- }
- ll mn_xor(ll n){
- Node* cur = root;
- ll ans = 0;
- for(ll i = 61 ; i >= 0 ; i--){
- ll bit = (n >> i) & 1;
- if(cur->child[bit]){
- cur = cur->child[bit];
- }else{
- ans |= (1ll << i);
- cur = cur->child[bit ^ 1];
- }
- }
- return ans;
- }
- };
- void solve(){
- BinaryTrie trie;
- int n;
- cin >> n;
- vector < vector < ll > > adj(n + 5);
- for(int i = 2 ; i <= n ; i++){
- int x;
- cin >> x;
- adj[x].push_back(i);
- }
- vector < ll > pow(n + 1) , ans(n + 1);
- for(int i = 1 ; i <= n ; i++) cin >> pow[i];
- function < void(int) > dfs = [&](int src){
- ans[src] = trie.mn_xor(pow[src]);
- trie.insert(pow[src]);
- for(auto & nxt : adj[src]){
- dfs(nxt);
- ans[src] = min(ans[src] , ans[nxt]);
- }
- trie.remove(pow[src] , 61 , trie.root);
- };
- trie.insert(-1);
- dfs(1);
- int q;
- cin >> q;
- while(q--){
- int x;
- cin >> x;
- cout << ans[x] << nl;
- }
- }
- int main() {
- Sira();
- int t = 1;
- // cin >> t;
- while(t--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement