[codeforces - 208e] blood cousins

Topic link
Enhanced example （ Not yet ）

The question ：

Given a tree $n$ A tree of nodes . give $m$ Time to ask , Give out... Every time you ask $x$ and $k$, ask $x$ How many $k$ Generation brother .（ The two points are $k$ The definition of generation brothers is their $k$ Same level ancestors ）
$1\le n,m\le 10^5$

practice ：

Take depth as the first keyword for all points ,$dfs$ The order is the second keyword . then $k$ Brother Dai must be in a continuous interval , In this way, it is transformed into an interval problem .

In this case , After arranging the order , Divide the left and right boundaries of inquiry point two , You can find all of it $k$ Generation brothers .
（ The enhanced version is for $k$ The third generation of brothers $k$ Big , Just use the chairman tree to maintain the interval ）

Code ：

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int>v[100005];
int id[100005],idx,dep[100005],fa[100005][20];
void dfs(int x,int pre)
{
    
    if(x==0)dep[x]=0,fa[x][0]=0;
    else dep[x]=dep[pre]+1,fa[x][0]=pre;
    if(x!=0)id[x]=++idx;
    for(auto to:v[x])
    {
    
        if(to!=pre)
        {
    
            dfs(to,x);
        }
    }
}

bool cmp(int a,int b)
{
    
    if(dep[a]!=dep[b])return dep[a]<dep[b];
    else return id[a]<id[b];
}

int getK(int x,int k)
{
    
    for(int i=0;i<=18;i++)if((k>>i)&1)x=fa[x][i];
    return x;
}

int idd[100005];
int wei[100005];
int main()
{
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    
        idd[i]=i;
        int x;
        scanf("%d",&x);
        v[x].push_back(i);
        v[i].push_back(x);
    }
    dfs(0,-1);
    for(int i=1;i<=18;i++)
    {
    
        for(int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];
    }
    sort(idd+1,idd+n+1,cmp);
    for(int i=1;i<=n;i++)wei[idd[i]]=i;
    int m;
    scanf("%d",&m);
    while(m--)
    {
    
        int x,k;
        scanf("%d%d",&x,&k);
        int f=getK(x,k);
        if(f==0){
    printf("%d\n",0);continue;}
        int led,red;
        int l=1,r=wei[x];
        while(l<r)
        {
    
            int p=(l+r)/2;
            if(getK(idd[p],k)==f)r=p;
            else l=p+1;
        }
        led=l;

        l=wei[x],r=n;
        while(l<r)
        {
    
            int p=(l+r+1)/2;
            if(getK(idd[p],k)==f)l=p;
            else r=p-1;
        }
        red=l;

        printf("%d\n",red-led+1-1);
    }
    return 0;
}