（hdu）5423 Rikka with Tree （dfs）

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5423

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  and vertice i.(The length of each edge is ).

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  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  testcases.

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

Then n− lines follow. Each line contains two numbers u,v(≤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

Sample Output

YES

NO

题意：两棵树中所有点到根节点的距离都相同时这两棵树叫做相似的树，两棵树中有某个节点的父节点不同时这两棵树叫不同的数，如果一棵树不存在另一棵树与之不同且相似则称这棵树为特殊的树，给出一棵树判断是否为特殊的树

方法：先分层，在判断是一条直树，还是扫帚型的

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <queue>

 #include <math.h>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define ll long long

 #define met(a,b) memset(a,b,sizeof(a));

 #define N 1034

 int Map[N][N];

 int con[N];

 int n;

 void bfs(int s,int m)

 {

     con[s]=m;

     for(int i=;i<=n;i++)

     {

         if(Map[s][i]&&!con[i])

         {

             bfs(i,m+);

         }

     }

 }

 int main()

 {

     int a,b;

     int sum[N];

     while(scanf("%d",&n)!=EOF)

     {

         met(Map,);met(con,);

         for(int i=;i<n;i++)

         {

             scanf("%d %d",&a,&b);

             Map[a][b]=Map[b][a]=;

         }

         bfs(,);///对树分层

         met(sum,);int ans=;

         for(int i=;i<=n;i++)

         {

             sum[con[i]]++;

         }

         for(int i=;i<=n;i++)

         {

             if(sum[i]==)///是否是一条线到底

                 ans++;

             else

             {

                 if(sum[i+]==)///是否是扫帚型

                     ans=n;

                     break;

             }

         }

         if(ans==n)

             printf("YES\n");

         else

             printf("NO\n");

     }

     return ;

 }