传送门
之前那道题的数据加强版，用线段树合并卡了很多次都过不去，很伤。
原因还是线段树合并时间常数太大了，这题可以dfs序+树状数组过的，常数就小很多了。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,dep[N],ans[N],fa[N][15],rt[N],mdep;
int head[N],to[N*2],nxt[N*2],tot;
void add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
int qhead[N],qto[N],qid[N],qnxt[N],qtot;
void qadd(int u,int v,int id){qto[++qtot]=v;qid[qtot]=id;qnxt[qtot]=qhead[u];qhead[u]=qtot;}
static char buf[100000],*a=buf,*d=buf;
#define gc a==d&&(d=(a=buf)+fread(buf,1,100000,stdin),a==d)?EOF:*a++
inline int read(){
register int x(0);register char c(gc);
while(c>'9'||c<'0')c=gc;
while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+(c^48),c=gc;
return x;
}
struct SegTrees{
#define mid (l+r>>1)
int sta[N*4],top;
int sum[N*4],ls[N*4],rs[N*4],tot;
int newnode(){if(!top) return ++tot;return sta[top--];}
void delnode(int id){sum[id]=ls[id]=rs[id]=0;sta[++top]=id;}
void upd(int &id,int l,int r,int pos){
if(!id) id=newnode();
if(l==r) {sum[id]++;return;}
if(pos<=mid) upd(ls[id],l,mid,pos);
else upd(rs[id],mid+1,r,pos);
sum[id]=sum[ls[id]]+sum[rs[id]];
}
void merge(int &x,int y,int l,int r){
if(!x||!y) {x=x+y;return;}
if(l==r) {sum[x]+=sum[y];delnode(y);return;}
merge(ls[x],ls[y],l,mid);
merge(rs[x],rs[y],mid+1,r);
sum[x]=sum[ls[x]]+sum[rs[x]];
delnode(y);
}
int ask(int id,int l,int r,int pos){
if(!id) return 0;
if(l==r) return sum[id];
if(pos<=mid) return ask(ls[id],l,mid,pos);
else return ask(rs[id],mid+1,r,pos);
}
#undef mid
}trs;
void predfs(int u,int rt){
fa[u][0]=rt;dep[u]=dep[rt]+1;mdep=max(mdep,dep[u]);
for(int i=head[u];i;i=nxt[i]) if(to[i]!=rt) predfs(to[i],u);
}
void dfs(int u,int fa){
trs.upd(rt[u],1,mdep,dep[u]);
for(int i=head[u];i;i=nxt[i]){
if(to[i]==fa) continue;
dfs(to[i],u);
trs.merge(rt[u],rt[to[i]],1,mdep);
}
for(int i=qhead[u];i;i=qnxt[i]) ans[qid[i]]=trs.ask(rt[u],1,mdep,qto[i]);
}
int main(){
// freopen("data.in","r",stdin);
n=read();m=read();
for(int i=2;i<=n;i++){
int u=read();
add(u,i);add(i,u);
}
predfs(1,0);
for(int i=1;i<=14;i++) for(int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1];
for(int i=1;i<=m;i++){
int u=read(),k=read(),rt=u,temp=k;
for(int j=14;j>=0;j--) if(k>=(1<<j)) rt=fa[rt][j],k-=(1<<j);
qadd(rt,dep[rt]+temp,i);
}
dfs(1,0);
for(int i=1;i<=m;i++) printf("%d ",ans[i]?ans[i]-1:0);
return 0;
}
更新一下通过代码，直接dfs然后差分记录答案就行了，处理二维问题的思路。
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define x first
#define y second
using namespace std;
const int N=1e6+10;
typedef pair<int,int> PII;
int n,m,fa[N][15];
int head[N],to[N],nxt[N],tot,dep[N],ans[N],cnt[N];
void add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
int qhead[N],qto[N],qid[N],qnxt[N],qtot;
void qadd(int u,int v,int id){qto[++qtot]=v;qid[qtot]=id;qnxt[qtot]=qhead[u];qhead[u]=qtot;}
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x*f;
}
void predfs(int u,int rt){
dep[u]=dep[rt]+1;fa[u][0]=rt;
for(int i=head[u];i;i=nxt[i]) predfs(to[i],u);
}
void dfs(int u){
for(int i=qhead[u];i;i=qnxt[i]) ans[qid[i]]-=cnt[qto[i]];
cnt[dep[u]]++;
for(int i=head[u];i;i=nxt[i]) dfs(to[i]);
for(int i=qhead[u];i;i=qnxt[i]) ans[qid[i]]+=cnt[qto[i]];
}
int main(){
n=read(),m=read();
for(int i=2,u;i<=n;i++) u=read(),add(u,i);
predfs(1,0);
for(int i=1;i<15;i++) for(int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1];
for(int i=1,u,k;i<=m;i++){
u=read(),k=read();
for(int j=0;j<15;j++) if((k>>j)&1) u=fa[u][j];
qadd(u,dep[u]+k,i);
}
dfs(1);
for(int i=1;i<=m;i++) printf("%d ",ans[i]?ans[i]-1:0);
return 0;
}