Untitled
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