526互联

[ABC202E] Count Descendants 题解

发布时间 2023-06-05 13:31:06作者: TKXZ133

Count Descendants

题目大意

给定一颗以 \(1\) 为根的树，多次询问求某点的子树中深度为给定值的点的个数。

思路分析

对于每个深度开一个 vector，从大到小存下这个深度的所有点的 dfs 序开始值和结束值，询问时只需要在对应深度的 vector 中二分作差即可。

代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N=400100;

int to[N],nxt[N],head[N];
int n,idx=1,cnt,q,in1,in2;
int dfn[N],dep[N],End[N];

vector<int> v[N];

void add(int u,int v){
    idx++;to[idx]=v;nxt[idx]=head[u];head[u]=idx;
}

void dfs(int s,int fa){
    dfn[s]=++cnt;
    dep[s]=dep[fa]+1;
    v[dep[s]].push_back(dfn[s]);
    for(int i=head[s];i;i=nxt[i]){
        int v=to[i];
        if(v==fa) continue;
        dfs(v,s);
    }
    End[s]=++cnt;
}

int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        scanf("%d",&in1);
        add(i,in1);add(in1,i);
    }
    dfs(1,0);
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&in1,&in2);in2++;
        cout<<lower_bound(v[in2].begin(),v[in2].end(),End[in1])-lower_bound(v[in2].begin(),v[in2].end(),dfn[in1]-1)<<'\n';
    }
    return 0;
}