HDU 4707 Pet （热身赛第二题）

转载请注明出处：http://blog.csdn.net/a1dark

分析：读懂题意之后很简单的一个搜索、在D之外的个数有多少个、

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<queue>using namespace std;struct node{    int s,e;    int next;}cnt[100005*4];int root[100005];int vis[100005];int dis[100005];int ans,n,num,T;void add(int s,int e){    cnt[++ans].e=e;    cnt[ans].next=root[s];    root[s]=ans;}void bfs(){    queue<int>q;    q.push(0);    vis[0]=1;    dis[0]=1;    int s,e,i;    while(!q.empty()){        s=q.front();        if(dis[s]==T+2)            break;        q.pop();        for(i=root[s];i!=-1;i=cnt[i].next){            e=cnt[i].e;            if(!vis[e]){                vis[e]=1;                dis[e]=dis[s]+1;                q.push(e);            }        }    }    for(i=0;i<n;i++){        if(dis[i]==T+2 || dis[i]==0)            num++;    }}int main(){    int t;    scanf("%d",&t);    while(t--){        num=0;        memset(root,-1,sizeof(root));        memset(vis,0,sizeof(vis));        memset(dis,0,sizeof(dis));        ans=-1;        scanf("%d%d",&n,&T);        for(int i=0;i<n-1;i++){            int s,e;            scanf("%d%d",&s,&e);            add(s,e);        }        bfs();        printf("%d\n",num);    }    return 0;}