本文主要是介绍Blood Cousins CodeForces - 208E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://codeforces.com/problemset/problem/208/E
问一个节点v有多少p兄弟 就等于看v的p祖先有多少p孩子
找p祖先就倍增或者树剖一下 然后就是某一层的节点中属于某棵子树的点有多少 用dfs序一判即可
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn=1e5+10;struct node
{int v,next;
};vector <int> pre[maxn];
node edge[maxn];
int first[maxn],fa[maxn],deep[maxn],sum[maxn],son[maxn],top[maxn],mp1[maxn],mp2[maxn];
int n,q,num;void addedge(int u,int v)
{edge[num].v=v;edge[num].next=first[u];first[u]=num++;
}void dfsI(int cur)
{int i,v;sum[cur]=1,son[cur]=-1;for(i=first[cur];i!=-1;i=edge[i].next){v=edge[i].v;if(v!=fa[cur]){deep[v]=deep[cur]+1;dfsI(v);sum[cur]+=sum[v];if(son[cur]==-1||sum[son[cur]]<sum[v]){son[cur]=v;}}}
}void dfsII(int cur,int tp)
{int i,v;num++;top[cur]=tp,mp1[cur]=num,mp2[num]=cur;pre[deep[cur]].pb(mp1[cur]);if(son[cur]==-1) return;dfsII(son[cur],tp);for(i=first[cur];i!=-1;i=edge[i].next){v=edge[i].v;if(v!=fa[cur]&&v!=son[cur]){dfsII(v,v);}}
}int getpos(int u,int dep)
{int tmp;while(deep[top[u]]>dep){u=fa[top[u]];}tmp=deep[u]-dep;return mp2[mp1[u]-tmp];
}int main()
{int i,v,p,pl,pr,gou;scanf("%d",&n);memset(first,-1,sizeof(first));num=0;for(i=1;i<=n;i++){scanf("%d",&fa[i]);if(fa[i]!=0){addedge(fa[i],i);}}num=0;for(i=1;i<=n;i++){if(fa[i]==0){deep[i]=1;dfsI(i);dfsII(i,i);}}/*for(i=1;i<=n;i++){sort(pre[i].begin(),pre[i].end());for(int j=0;j<pre[i].size();j++){printf("%d ",pre[i][j]);}printf("\n");}*/scanf("%d",&q);while(q--){scanf("%d%d",&v,&p);gou=deep[v];if(deep[v]-p<1){printf("0\n");continue;}v=getpos(v,deep[v]-p);//printf("***%d %d***\n",v,deep[v]);pl=lower_bound(pre[gou].begin(),pre[gou].end(),mp1[v])-pre[gou].begin();pr=upper_bound(pre[gou].begin(),pre[gou].end(),mp1[v]+sum[v]-1)-pre[gou].begin();printf("%d ",pr-pl-1);}printf("\n");return 0;
}
这篇关于Blood Cousins CodeForces - 208E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
