| 记录编号 |
612533 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
树上查询 |
最终得分 |
100 |
| 用户昵称 |
 RpUtl |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
34.599 s |
| 提交时间 |
2026-02-13 23:52:23 |
内存使用 |
633.81 MiB |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
namespace IO{
int len = 0;
char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 25) + 1];
#define gh() \
(iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin),\
(iS == iT ? EOF : *iS++) : *iS++)
#define reg register
template <class T> inline void read(T &x){
reg char ch = gh();
reg char t = 0; x = 0;
while (ch < '0' || ch > '9')
t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9')
x = x * 10 + (ch ^ 48), ch = gh();
if (t) x = -x;
return;
}
inline void putc(char ch){
out[len++] = ch;
}
template <class T> inline void write(T x){
if (x < 0) putc('-'), x = -x;
if (x > 9) write(x / 10);
out[len++] = x % 10 + 48;
}
inline void flush(){
fwrite(out, 1, len, stdout); len = 0;
}
}
using IO::flush;
using IO::putc;
using IO::read;
using IO::write;
typedef long long ll;
const int N=1e6+10;
int n,q,a[N],ver[N],to[N],nxt[N],idx,son[N],tp[N];
int dfn[N],dep[N],k[N],cnt,pos[N];
ll f[21][N],g[2][31][N],ans[N];
vector<int>Q[N];
void add(int x,int y){
to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx;
}
void dfs1(int x){
dep[x]=1;
for(int i=ver[x],y;i;i=nxt[i]){
y=to[i],dfs1(y);
if(dep[y]>dep[son[x]])son[x]=y;
}
dep[x]=dep[son[x]]+1;
return;
}
void dfs2(int x,int top){
dfn[x]=++cnt,tp[x]=top;
if(!son[x])return;
dfs2(son[x],top);
for(int i=ver[x],y;i;i=nxt[i]){
y=to[i];if(y==son[x])continue;
dfs2(y,y);
}
return;
}
ll book[2][31];
void DFS(int x){
if(son[x])DFS(son[x]);
//if(x==6)cout<<"SSSSSSSSSSSSSSSSSSSS"<<g[0][4][dfn[6]]<<endl;
for(int i=ver[x],y;i;i=nxt[i]){
y=to[i];if(y==son[x])continue;
DFS(y);
for(int i=0;i<dep[y];i++){
for(int j=0;j<=30;j++){
g[0][j][dfn[x]+i+1]+=g[0][j][dfn[y]+i];
g[1][j][dfn[x]+i+1]+=g[1][j][dfn[y]+i];
if(j<=20)f[j][dfn[x]+i+1]+=f[j][dfn[y]+i];
//if(x==6)cout<<"SSSSSSSSSSSSSSSSSSSS"<<g[0][4][dfn[6]]<<" "<<i<<" "<<j<<endl;
}
}
}
// if(x==6)cout<<g[0][4][dfn[6]]<<endl;
for(int j=0;j<=30;j++){
if((a[x]>>j)&1)g[1][j][dfn[x]]++;
else g[0][j][dfn[x]]++;
if(dep[x]>1){
//if(x==6&&j==4)cout<<g[0][j][dfn[x]]<<" ------------------------- "<<g[0][j][dfn[x]+1]<<endl;
g[1][j][dfn[x]]+=g[1][j][dfn[x]+1];
g[0][j][dfn[x]]+=g[0][j][dfn[x]+1];
}
}
// if(x){
// cout<<"--------------"<<x<<endl;
// for(int i=0;i<dep[x];i++){
// for(int j=0;j<=30;j++){
// cout<<i<<" "<<j<<" "<<g[0][j][dfn[x]+i]<<" "<<g[1][j][dfn[x]+i]<<endl;
// }
// }
// }
int u,v,r,nxt;ll c1,c0;
for(int j=0,lll=dfn[x]+dep[x];j<=30;j++){
book[0][j]=g[0][j][lll],g[0][j][lll]=0;
book[1][j]=g[1][j][lll],g[1][j][lll]=0;
}
for(int j=1,lim=dfn[x]+dep[x];j<=20;j++){
u=dfn[x]+(1<<(j-1))-1,v=dfn[x]+(1<<j)-1;
f[j][dfn[x]]=f[j-1][dfn[x]]+(u+1<lim?f[j-1][u+1]:0);
c1=g[1][j-1][dfn[x]]-(u+1<lim?g[1][j-1][u+1]:0);
c0=(u+1<lim?g[0][j-1][u+1]:0)-(v+1<lim?g[0][j-1][v+1]:0);
f[j][dfn[x]]+=(c1+c0)*(1ll<<(j-1));
}
// if(x==6)cout<<"Sssss"<<f[1][dfn[x]]<<" "<<dfn[x]<<endl;
// if(x==1)cout<<"Sssss"<<f[1][dfn[x]+2]<<" "<<dfn[x]+2<<endl;
for(auto i:Q[x]){
k[i]=min(k[i]+1,dep[x]);
u=dfn[x],r=u+k[i]-1;
for(int j=30;j>=0;j--){
if((k[i]>>j)&1){
nxt=u+(1<<j);ans[i]+=f[j][u];
// if(x==1&&j==2)cout<<"----"<<k[i]<<" "<<f[j][u]<<endl;
c1=g[1][j][u]-g[1][j][nxt]; //[u,nxt-1]
c0=g[0][j][nxt]-g[0][j][r+1];//[nxt,r]
ans[i]+=(c1+c0)*(1ll<<j);u=nxt;
// if(x==2)cout<<i<<" "<<g[1][1][u]<<" "<<g[1][1][u+2]<<endl;
}else{
ans[i]+=(g[1][j][u]-g[1][j][r+1])*(1ll<<j);// [u,r]
}
}
}
for(int j=0,lll=dfn[x]+dep[x];j<=30;j++){
g[0][j][lll]=book[0][j],book[0][j]=0;
g[1][j][lll]=book[1][j],book[1][j]=0;
}
return;
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
read(n);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=2,p;i<=n;i++)read(p),add(p,i);
read(q);dfs1(1),dfs2(1,1);
for(int i=1,x;i<=q;i++){
read(x),read(k[i]);
Q[x].push_back(i);
}
DFS(1);
for(int i=1;i<=q;i++){
write(ans[i]);putc('\n');
}
flush();
return 0;
}