hdu 5432

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

For a tree T , let F(T,i) be the distance between vertice 1 and vertice i .(The length of each edge is 1).

Two trees A and B are similiar if and only if the have same number of vertices and for each i meet F(A,i)=F(B,i) .

Two trees A and B are different if and only if they have different numbers of vertices or there exist an number i which vertice i have different fathers in tree A and tree B when vertice 1 is root.

Tree A is special if and only if there doesn't exist an tree B which A and B are different and A and B are similiar.

Now he wants to know if a tree is special.

It is too difficult for Rikka. Can you help her?

 

Input

There are no more than 100 testcases.

For each testcase, the first line contains a number n(1≤n≤1000) .

Then n−1 lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v .

 

Output

For each testcase, if the tree is special print "YES" , otherwise print "NO".

 

Sample Input

3 1 2 2 3 4 1 2 2 3 1 4

 

Sample Output

YES NO

Hint

For the second testcase, this tree is similiar with the given tree: 4 1 2 1 4 3 4

 

 

题意就是每层数只能有一个节点（除了最后一层的节点）

多于这种多个数需要记录其中每个数出现的次数的情况  灵活的使用标记数组

#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
struct node
{
 int x,y;
}stu;
int main()
{
 int num[1001],ans[1001];
 int i,j,t,x,y;
 while(cin>>t)
 {
  queue<node>q;
  node tt;
  memset(num,0,sizeof(num));
  memset(ans,0,sizeof(ans));
  num[1]=1;
     for(j=1;j<t;j++)
     {
      cin>>stu.x>>stu.y;
      if(num[stu.x]!=0)
   {
    num[stu.y]=num[stu.x]+1;
    continue;
   }
      if(num[stu.y]!=0)
   {
    num[stu.x]=num[stu.y]+1;
    continue;
   }
      if(num[stu.x]==0&&num[stu.y]==0)
   {
    q.push(stu);
    continue;
   }
      }
      while(!q.empty())
      {
       tt=q.front();
       q.pop();
       if(num[tt.x]!=0)
      {
        num[tt.y]=num[tt.x]+1;
        continue;
      }
      if(num[tt.y]!=0)
   {
        num[tt.x]=num[tt.y]+1;
     continue; 
   }
   if(num[tt.x]==0&&num[tt.y]==0)
         {
    q.push(tt);
    continue;
   }
      }
      int maxx=0;
      for(i=1;i<=t;i++)
      {
         ans[num[i]]++;
    //     cout<<ans[num[i]]<<endl;
         if(maxx<num[i]) maxx=num[i];
      }
      int flag=1;
      for(j=maxx-1;j>=1;j--)
      {
      // cout<<ans[j]<<endl;
       if(ans[j]>1)
       {
        flag=0;
        break;
       }
      }
      if(flag==0) cout<<"NO"<<endl;
      else cout<<"YES"<<endl;
 }
 return 0;
}

附上代码 少年  调整好心态 做一件的时候尽可能的去做到一直专注 抹去那些杂念  去杂  本身就是一种能力