atcoder-ABC202-E

atcoder-abc202-E

题意：维护以i为根的子树上深度为k的节点个数。

题解：正常的做法大概是基础的dfs序+主席树维护深度。赛场上看到了码量小了很多的做法，记录一下这种神奇的思路。

考虑对于每个深度存储每个节点的dfs序编号，回答询问的时候只需要二分寻找给定深度中编号≥dfn[now]&&≤dfn[now]+siz[now]-1的编号数目即可。大概是利用了深度是唯一的这样一个特点，不然这个做法不能通过。

int siz[maxn],dfn[maxn],rdfn[maxn],tot,totd,n;
vector<int> yuan[maxn],cun[maxn];
void dfs(int now,int fa,int dep){
    dfn[now]=++tot;rdfn[tot]=now;
    siz[now]=1;
    totd=max(totd,dep);
    cun[dep].push_back(dfn[now]);
    for(int i=0;i<yuan[now].size();i++){
        int v=yuan[now][i];
        if(v==fa) continue;
        dfs(v,now,dep+1);
        siz[now]+=siz[v];
    }
}
ll req(int now1,int now2,int dep){
    return upper_bound(cun[dep].begin(),cun[dep].end(),now2)-lower_bound(cun[dep].begin(),cun[dep].end(),now1);
}
signed main(){
    ios;cin>>n;
    for(int i=2;i<=n;i++){
        int a1;cin>>a1;
        yuan[i].push_back(a1);yuan[a1].push_back(i);
    }
    dfs(1,0,1);
    int q;cin>>q;
    while(q--){
        int a1,a2;cin>>a1>>a2;a2++;
        cout<<req(dfn[a1],dfn[a1]+siz[a1]-1,a2)<<endl;
    }
    return 0;
}

atcoder-ABC202-E

原文：https://www.cnblogs.com/14long-Alex/p/14800173.html