題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5423

題面：

Rikka with Tree Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 667????Accepted Submission(s): 306


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 numberi 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 HintFor the second testcase, this tree is similiar with the given tree: 4 1 2 1 4 3 4

解題：

??? 題目意思也是蠻繞的。相似是指，兩棵樹頂點(diǎn)數(shù)相同，且每個(gè)點(diǎn)到根節(jié)點(diǎn)（1為根節(jié)點(diǎn)）的距離都相同。不同是指，頂點(diǎn)數(shù)不同或者兩棵樹上某個(gè)節(jié)點(diǎn)的父親不一樣?，F(xiàn)要求判斷一棵樹是不是special，special的特征是，不存在與之相似或與之不同的樹。一開始有點(diǎn)混，以為只要是鏈即可。實(shí)際上，這樣會漏掉兩種情況，鏈?zhǔn)遣幌嗨?，且不不同的情況，應(yīng)該是去找是否存在不同且相似的情況。存在輸出“NO”，否則輸出“YES”。

??? 那么什么是不同且相似呢？就是某個(gè)節(jié)點(diǎn)它有超過1個(gè)孩子，并且它至少還可以往下兩層。那么，假設(shè)當(dāng)前節(jié)點(diǎn)在x層，其左右孩子分別為a，b，b還有孩子，那么交換a，b的孩子。對于新的到的樹，就是不同且相似的，即每個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)距離不變，但交換的孩子的父親發(fā)生了改變。

代碼：

#include 
#include 
#include 
using namespace std;
struct edge
{
	int next,to;
}store[2010];
int head[1005],cnt;
bool vis[1005];
//加一條從a到b的邊
void addedge(int a,int b)
{
	//cnt為邊的存儲下標(biāo)
	store[cnt].to=b;
	store[cnt].next=head[a];
	//head為個(gè)頂點(diǎn)指向的第一條邊的下標(biāo)
	head[a]=cnt++;
}
bool flag;
//flag為標(biāo)記，y為上一點(diǎn)是否有超過一個(gè)孩子的標(biāo)記
void dfs(int x,bool y)
{
	if(flag)return;
	//標(biāo)記該點(diǎn)
	vis[x]=1;
	//如果上一節(jié)點(diǎn)有超過一個(gè)孩子
	if(y)
	{
		int num=0,tmp=head[x];
		while(tmp!=-1)
		{
			//那么只要當(dāng)前節(jié)點(diǎn)還有孩子即可
			if(!vis[store[tmp].to])
			{
				flag=true;
				return;
			}
			tmp=store[tmp].next;
		}
	}
	//如果沒有，就繼續(xù)向下移
	else
	{
	  int tmp=head[x],num=0;
	  //數(shù)當(dāng)前節(jié)點(diǎn)孩子數(shù)量
	  while(tmp!=-1)
	  {
	    if(!vis[store[tmp].to])
			num++;
		tmp=store[tmp].next;
	  }
	  //如果孩子數(shù)量大于1
	  if(num>1)
	  {
		  int tmp=head[x];
		  while(tmp!=-1)
		  {
			  if(!vis[store[tmp].to])
				  dfs(store[tmp].to,1);
			  tmp=store[tmp].next;
		  }
	  }
	  //如果孩子數(shù)量小于等于1
	  else
	  {
         int tmp=head[x];
		  while(tmp!=-1)
		  {
			  if(!vis[store[tmp].to])
				  dfs(store[tmp].to,0);
			  tmp=store[tmp].next;
		  }
	  }
	}
}
int main()
{
    int n,a,b;
	while(~scanf("%d",&n))
	{
	   memset(vis,0,sizeof(bool)*(n+1));
	   memset(head,-1,sizeof(int)*(n+1));
       cnt=0;
       for(int i=1;i1)
         dfs(1,1);
	   else
		 dfs(1,0);
	   if(flag)printf("NOn");
	   else printf("YESn");
	}
	return 0;
}