CF 208E

倍增求LCA模板

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 100100
using namespace std;
vector<int>vec,vec1[N];
int head[N],cnt;
struct Edge{
    int v,next;
}edge[N];
int tim,fa[N],b[N],son[N],dep[N],p[N][18];
int ans[N];
void init(){
    vec.clear();
    memset(head,-1,sizeof(head));
    memset(dep,0,sizeof(dep));
    memset(p,0,sizeof(p));
    memset(son,0,sizeof(son));
    cnt=tim=0;
}
void addedge(int u,int v){
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void dfs(int u){
    int i;
    b[u]=++tim;
    dep[u]=dep[fa[u]]+1;
    vec1[dep[u]].push_back(tim);
    p[u][0]=fa[u];
    for(i=1;i<18;i++)p[u][i]=p[p[u][i-1]][i-1];
    son[u]=1;
    for(i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        dfs(v);
        son[u]+=son[v];
    }
}
int find(int u,int num){    //返回u的第num代祖先
    for(int i=0;i<18;i++)
        if((1<<i)&num)
            u=p[u][i];
    return u;
}
int solve(int t,int num){   //二分查找区间[0,vec1[num].size()-1]内vec1[num][i]<=t中最大的i
    int h=vec1[num].size()-1,l=0,sum=-1;
    while(l<=h){
        int mid=(h+l)>>1;
        if(vec1[num][mid]>t)
            h=mid-1;
        else{
            sum=mid;
            l=mid+1;
        }
    }
    return sum;
}
int main(){
    int i,v,n,m,num;
    init();
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&v);
        fa[i]=v;
        if(v==0)vec.push_back(i);
        addedge(v,i);
    }
    for(i=0;i<vec.size();i++)
        dfs(vec[i]);
    scanf("%d",&m);
    for(i=1;i<=m;i++){
        scanf("%d %d",&v,&num);
        int u=find(v,num);
        if(!u)ans[i]=0;
        else ans[i]=solve(b[u]+son[u]-1,dep[v])-solve(b[u]-1,dep[v])-1;
    }
    for(i=1;i<=m;i++)
        if(i==1)printf("%d",ans[i]);
        else printf(" %d",ans[i]);
    printf("\n");
	return 0;
}