Untitled
unknown
plain_text
a year ago
3.1 kB
14
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