Untitled

 avatar
unknown
plain_text
a year ago
3.1 kB
7
Indexable
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Trie {
    static const int B = 62;
    struct node {
        node* nxt[2];
        int sz;
        node() {
            nxt[0] = nxt[1] = nullptr;
            sz = 0;
        }
    }*root;
    Trie() {
        root = new node();
    }
    void insert(int val) {
        node* cur = root;
        cur -> sz++;
        for (int i = B - 1; i >= 0; i--) {
            int b = val >> i & 1;
            if (cur -> nxt[b] == nullptr) cur -> nxt[b] = new node();
            cur = cur -> nxt[b];
            cur -> sz++;
        }
    }
    void erase(int val) {
        node* cur = root;
        cur -> sz--;
        for (int i = B - 1; i >= 0; i--) {
            int b = val >> i & 1;
            if (cur -> nxt[b] ==nullptr) cur -> nxt[b] = new node();
            cur = cur -> nxt[b];
            cur -> sz--;
        }
    }
    int query(int x, int k) { // number of values s.t. val ^ x < k
        node* cur = root;
        int ans = 0;
        for (int i = B - 1; i >= 0; i--) {
            if (cur == nullptr) break;
            int b1 = (x >> i) & 1, b2 = (k >> i) & 1;
            if (b2 == 1) {
                if (cur -> nxt[b1]) ans += cur -> nxt[b1] -> sz;
                cur = cur -> nxt[!b1];
            } else cur = cur -> nxt[b1];
        }
        return ans;
    }
    int get_max(int x) { // returns maximum of val ^ x
        node* cur = root;
        int ans = 0;
        for (int i = B - 1; i >= 0; i--) {
            int k = x >> i & 1;
            if (cur -> nxt[!k]) cur = cur -> nxt[!k], ans <<= 1, ans++;
            else cur = cur -> nxt[k], ans <<= 1;
        }
        return ans;
    }
    int get_min(int x) { // returns minimum of val ^ x
        node* cur = root;
        int ans = 0;
        for (int i = B - 1; i >= 0; i--) {
            int k = x >> i & 1;
            if (cur -> nxt[k] && cur -> nxt[k] -> sz) cur = cur -> nxt[k], ans <<= 1;
            else cur = cur -> nxt[!k], ans <<= 1, ans++;
        }
        return ans;
    }
    void del(node* cur) {
        for (int i = 0; i < 2; i++) if (cur -> nxt[i]) del(cur -> nxt[i]);
        delete(cur);
    }
}trie ;
void dfs(int node,int p,vector<vector<int>>&adj,vector<int>&val,vector<int>&dp)
{
    if (node!=0) {
        trie.insert(val[p]);
        dp[node] = trie.get_min(val[node]);
    }
    bool ok=true;
    for (auto t:adj[node])
    {
        if (t==p)continue;
        ok=false;
        dfs(t,node,adj,val,dp);
        dp[node]=min(dp[node],dp[t]);
    }
    if(!ok)
        trie.erase(val[node]);
}
signed main()
{
    int n;
    cin>>n;
    vector<vector<int>>adj(n);
    for (int i=1;i<n;++i)
    {
        int x;
        cin>>x;
        x--;
        adj[i].push_back(x);
        adj[x].push_back(i);
    }
    vector<int>val(n),dp(n);
    for (int i=0;i<n;++i)cin>>val[i];
    dfs(0,-1,adj,val,dp);
    dp[0]=val[0];
    for (auto t:adj[0])
    {
        dp[0]=min(dp[0],dp[t]);
    }
    int q;
    cin>>q;
    while(q--)
    {
        int u;
        cin>>u;
        --u;
        cout<<dp[u]<<'\n';
    }
}
Editor is loading...
Leave a Comment