CF 208E Blood Cousins(2分+DFS)

CF 208E Blood Cousins(二分+DFS)

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by---cxlove

题目：给出一棵树，给出k-parent的定义，以及k-cousin的定义，求某个点的k-cousin有多少个。http://codeforces.com/problemset/problem/208/E 
我大概有了后半段的想法，然后yobobobo提供了前半段的想法。很成功的一次合作，然后我也成功地实现了。大概是这样的，先来一次DFS将所有的顶点按DFS序标号，那么某棵子树的顶点标号就是一个连续区间。然后记录每一个结点的层数，然后把每一层的标号按顺序存储，这些在DFS的时候都可以完成。第一个问题是怎么获得某个结点的k-parent。我们有了当前结点的DFS标号，然后知道k-parent的层数，以及这一层的所有结点。可以发现k-parent是标号恰好比当前结点小的，所以一次二分就可以解决 。那么接下来是找k-parent的子树中第k层的。那么就在这一层的结点中继续二分。因为我们有DFS序，知道某个子树的标号区间。就解决问题了

#include<iostream>    #include<cstdio>    #include<map>    #include<cstring>    #include<cmath>    #include<vector>    #include<stack>  #include<algorithm>    #include<set>    #include<string>    #include<queue>    #define inf 1000000005  #define M 1000005    #define N 100005  #define maxn 2000005    #define eps 1e-7  #define zero(a) fabs(a)<eps    #define Min(a,b) ((a)<(b)?(a):(b))    #define Max(a,b) ((a)>(b)?(a):(b))    #define pb(a) push_back(a)    #define mp(a,b) make_pair(a,b)    #define mem(a,b) memset(a,b,sizeof(a))    #define LL long long    #define MOD 1000000007  #define lson step<<1  #define rson step<<1|1  #define sqr(a) ((a)*(a))    #define Key_value ch[ch[root][1]][0]    #define test puts("OK");  #define pi acos(-1.0)  #define lowbit(x) ((x)&(-(x)))  #pragma comment(linker, "/STACK:1024000000,1024000000")    using namespace std; int n;int pre[N];vector<int>edge[N];int num[N],l[N],r[N],a[N];int dep[N],tot=0;vector<int>d[N];void dfs(int fa,int u,int depth){    dep[u]=depth;    num[u]=++tot;    a[tot]=u;    l[u]=tot+1;    d[depth].pb(tot);    for(int i=0;i<edge[u].size();i++){        int v=edge[u][i];        dfs(u,v,depth+1);    }    r[u]=tot;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&pre[i]);        if(pre[i]){            edge[pre[i]].pb(i);        }    }    for(int i=1;i<=n;i++){        if(pre[i]==0)            dfs(0,i,1);    }    int q;    scanf("%d",&q);   // for(int i=1;i<=n;i++)    //    printf("d:%d n:%d l:%d r:%d\n",dep[i],num[i],l[i],r[i]);    while(q--){        int v,k;        scanf("%d%d",&v,&k);        int now=dep[v];        if(now-k<1) puts("0");        else{            now-=k;            int fa=*(upper_bound(d[now].begin(),d[now].end(),num[v])-1);            fa=a[fa];            int left=l[fa],right=r[fa];            now+=k;            int ans=lower_bound(d[now].begin(),d[now].end(),left)-d[now].begin();            ans=(upper_bound(d[now].begin(),d[now].end(),right)-d[now].begin()-1)-ans+1;            printf("%d\n",ans-1);        }    }    return 0;}

查看更多 下一篇