HDU 5423 Rikka with Tree （樹，詳解）

題目鏈接：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

解題：

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

??? 那么什么是不同且相似呢？就是某個節(jié)點它有超過1個孩子，并且它至少還可以往下兩層。那么，假設(shè)當前節(jié)點在x層，其左右孩子分別為a，b，b還有孩子，那么交換a，b的孩子。對于新的到的樹，就是不同且相似的，即每個節(jié)點到根節(jié)點距離不變，但交換的孩子的父親發(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為邊的存儲下標
	store[cnt].to=b;
	store[cnt].next=head[a];
	//head為個頂點指向的第一條邊的下標
	head[a]=cnt++;
}
bool flag;
//flag為標記，y為上一點是否有超過一個孩子的標記
void dfs(int x,bool y)
{
	if(flag)return;
	//標記該點
	vis[x]=1;
	//如果上一節(jié)點有超過一個孩子
	if(y)
	{
		int num=0,tmp=head[x];
		while(tmp!=-1)
		{
			//那么只要當前節(jié)點還有孩子即可
			if(!vis[store[tmp].to])
			{
				flag=true;
				return;
			}
			tmp=store[tmp].next;
		}
	}
	//如果沒有，就繼續(xù)向下移
	else
	{
	  int tmp=head[x],num=0;
	  //數(shù)當前節(jié)點孩子數(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;
}