暴力

• 对于点集 $S$ 的询问，取任意 $u\in S$ 并以它为根。
• 对于 $v \in S\backslash{u}$，将其和任意一个的祖先 $w$ 满足 $dis(w,v)\leq K$，连有向边 $(w,v)$。
• 那么 $u$ 能到达的集合就是 $u$ 的 $K$ 连通块集合。删去之后继续做直到连通块为空。

性质

• 考虑每次取 $S$ 中 $bfs$ 序最小的更新，那么连出的有向边 $(u,v)$ 都满足 $bfn_u
• 所以，存在一种方式，使得所有点的入点的 $bfn$ 都比它自己的 $bfn$ 小，连通性不变。
• 显然这图不会有环，一个点是连通块起点当且仅当没有和它距离 $\leq K$ 且 $bfn$ 比它小的点，答案为连通块起点数。

转化

• 问题转化为对于区间内每个点 $u$，有没有和 $u$ 距离 $\leq K$ 且 $bfn$ 比它小的点也在区间内。
• 可以求 最大的 $L[u]u$，满足和 $u$ 距离 $\leq K$ 且 $bfn$ 比它小的点。
• 那么设询问为 $l,r$，$u$ 是连通块起点当且仅当 $L[u]r$。

计算 $L,R$

• 考虑怎么算 $L$（$R$ 同理），$L[u]$ 要满足：$dis(L[u],u)\leq K,bfn_{L[u]}
• 通过点分治，将第一个条件改成 $dep$ 的限制。那么对于分治中心的不同子树，两点的距离即为 $dep$ 之和，双指针即可。
• 对于第二、三个条件，可以将 $u$ 这维放进线段树，维护区间 $bfn$ 的最小值，即可线段树上二分出前面第一个 $bfn$ 比它小的位置。
• 然而，直接做要把不同子树两两计算一遍，即使启发式合并每次合并两个子树也要多一个 $\log$。
• 可以发现，不需要强制要求两点在分治中心的不同子树，因为如果在一棵子树内，$dis(L[u],u)$ 只会变得更大。
• 现在就可以直接将所有子树中的点双指针 + 线段树了，时间复杂度 $O(nlog^2n)$。（实现时可以使用 $zkw$ 线段树减小常数）

计算答案

• 计算出了 $L,R$，需要计算答案。现在要计算满足以下条件的 $u$ 的个数：$l\leq u\leq r,L_ur$。
• 将第一个条件拆开，相当于求满足 $u\leq x,L_ur$ 的点的数量。
• 这就是一个三维偏序，$CDQ$ 分治 + 树状数组即可，设 $n,q$ 同阶，时间复杂度 $O(nlog^2n)$。
• 总时间复杂度 $O(nlog^2n)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> pii;
int n,Q,k,cnt,dep[310000],sz[310000],tot[310000],pos[310000];
int L[310000],R[310000],l[610000],r[610000];
int edgenum,vet[610000],Next[610000],Head[310000]; bool vis[310000];
void addedge(int u,int v){
    vet[++edgenum]=v;
    Next[edgenum]=Head[u];
    Head[u]=edgenum;
}
void dfs(int u,int f){
    int v; dep[u]=dep[f]+1;
    for (int e=Head[u];e;e=Next[e]){
        v=vet[e]; if (v==f) continue;
        dfs(v,u);
    }
}
int all,mn,rt;
void getrt(int u,int f){
    sz[u]=1; int tmp=0;
    for (int e=Head[u];e;e=Next[e])
        if (!vis[vet[e]]&&vet[e]!=f){
            getrt(vet[e],u);
            sz[u]+=sz[vet[e]]; tmp=max(tmp,sz[vet[e]]);
        }
    tmp=max(tmp,all-sz[u]);
    if (tmp<mn) mn=tmp,rt=u;
}
int N,tree[2410000];
inline void change(int x,int v){
    x+=N;
    while (x) tree[x]=min(tree[x],v),x>>=1;
}
inline void tclr(int x){
    x+=N;
    while (x) tree[x]=INF,x>>=1;
}
inline int suc(int x,int v){
    x+=N;
    while (x>1&&((x&1)||tree[x^1]>=v)) x>>=1;
    if (x==1) return n+1;
    x^=1;
    while (x<N) x<<=1,x|=tree[x]>=v;
    return x-N;
}
inline int pre(int x,int v){
    x+=N;
    while (x>1&&(!(x&1)||tree[x^1]>=v)) x>>=1;
    if (x==1) return 0;
    x^=1;
    while (x<N){
        x<<=1;
        x|=tree[x|1]<v;
    }
    return x-N;    
}
void getroot(int u,int nn){
    all=nn; mn=INF; rt=u;
    getrt(u,0);
}
int len; pii num[310000];
int head,tail; pii que[310000];
void bfs(int u){
    head=1; tail=1; int v,f;
    que[1]=pii(u,0); dep[u]=0;
    while (head<=tail){
        u=que[head].first; f=que[head].second; head++;
        num[++len]=pii(dep[u],u);
        for (int e=Head[u];e;e=Next[e]){
            v=vet[e]; if (vis[v]||v==f) continue;
            que[++tail]=pii(v,u); dep[v]=dep[u]+1;
        }
    }
}

void solve(int u){
    vis[u]=true;
    len=0;
    bfs(u);

    int i=1;
    for (int j=len;j>=1;j--){
        pii v=num[j];
        while (i<=len){
            pii u=num[i]; if (u.first+v.first>k) break;
            change(u.second,pos[u.second]); i++;
        }
        int x=v.second;
        int ll=pre(v.second,pos[v.second]),rr=suc(v.second,pos[v.second]);
        if (ll<x) L[x]=max(L[x],ll); if (rr>x) R[x]=min(R[x],rr);
    }
    for (int j=1;j<i;j++) tclr(num[j].second);

    int t=all,tmp;
    for (int e=Head[u];e;e=Next[e]){
        if (vis[vet[e]]) continue;
        tmp=(sz[vet[e]]<sz[u]?sz[vet[e]]:t-sz[u]);
        getroot(vet[e],tmp); solve(rt);
    }
}
struct node{
    int pos,v,l,r,op;
    node(){}
    node(int _pos,int _v,int _l,int _r,int _op):pos(_pos),v(_v),l(_l),r(_r),op(_op){}
    bool operator<(const node &a) const{ return l<a.l;}
} q[1510000],p[1510000];
inline bool cmp(const node &x,const node &y){ return x.v<y.v||x.v==y.v&&!x.op&&y.op;}
int t[310000];
inline void add(int x){
    for (;x;x-=x&-x) t[x]++;
}
inline int query(int x){
    int res=0;
    for (;x<=n+1;x+=x&-x) res+=t[x];
    return res;
}
inline void clr(int x){
    for (;x;x-=x&-x) t[x]=0;
}
int Ans[610000];
void solve(int l,int r){
    if (l==r) return;
    int mid=(l+r)>>1;
    solve(l,mid); solve(mid+1,r);
    int j=l; while (j<=mid&&q[j].op) j++;
    for (int i=mid+1;i<=r;i++)
        if (q[i].op){
            while (j<=mid&&q[j].l<=q[i].l-1){
                add(q[j].r);
                j++; while (j<=mid&&q[j].op) j++;
            }
            Ans[q[i].pos]+=query(q[i].r+1)*q[i].op;
        }
    for (int i=l;i<j;i++)
        if (!q[i].op) clr(q[i].r);

    merge(q+l,q+mid+1,q+mid+1,q+r+1,p+l);
    for (int i=l;i<=r;i++) q[i]=p[i];
}
char Getchar(){
    static char now[1<<20],*S,*T;
    if (T==S){
        T=(S=now)+fread(now,1,1<<20,stdin);
        if (T==S) return EOF;
    }
    return *S++;
}
int read(){
    int x=0,f=1;
    char ch=Getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=Getchar();
    }
    while (ch<='9'&&ch>='0') x=x*10+ch-'0',ch=Getchar();
    return x*f;
}
char pbuf[1<<20],*pp=pbuf;
void pc(const char c){
    if (pp-pbuf==(1<<20)) fwrite(pbuf,1,1<<20,stdout),pp=pbuf;
    *pp++=c;
}
void write(int x){
    static int sta[35];
    if (x<0){
        pc('-');
        x=-x;
    }
    int top=0;
    do{
        sta[top++]=x%10;
        x/=10;
    } while(x);
    while (top) pc(sta[--top]+'0');
}
void myfflush(){
    fwrite(pbuf,1,pp-pbuf,stdout);
}

int main(){
    n=read(); Q=read(); k=read();
    int f;
    for (int i=2;i<=n;i++){
        f=read();
        addedge(f,i); addedge(i,f);
    }

    dfs(1,0);
    for (int i=1;i<=n;i++) tot[dep[i]]++;
    for (int i=1;i<=n;i++) tot[i]+=tot[i-1];
    for (int i=n;i>=1;i--) pos[i]=tot[dep[i]]--;
    memset(tree,0x3f,sizeof(tree));
    N=4;
    while (N-2<n) N<<=1;
    for (int i=1;i<=n;i++) L[i]=0,R[i]=n+1;
    getroot(1,n); solve(rt);
    for (int i=1;i<=n;i++) q[++cnt]=node(0,i,L[i],R[i],0);
    for (int i=1;i<=Q;i++){
        l[i]=read(); r[i]=read();
        q[++cnt]=node(i,l[i]-1,l[i],r[i],-1); q[++cnt]=node(i,r[i],l[i],r[i],1);
    }
    sort(q+1,q+cnt+1,cmp);
    solve(1,cnt);
    for (int i=1;i<=Q;i++) write(Ans[i]),pc('\n');
    myfflush();
    return 0;
}