http://acm.hdu.edu.cn/showproblem.php?pid=5423
题目大意：给你一个树 判断这棵树是否是独特的
一颗树是独特的条件：不存在一颗和它本身不同但相似的树
两颗树相似条件：两颗树中点的数量相等且相对应的点的深度相同
如第2个样例
4
1 2
2 3
1 4
与
4
1 2
1 4
3 4
如图：这两棵树的点的数量相等且相应的点的深度deep相同，所以这两棵树相似，所以样例2存在一颗树与它不同但相似，即不特殊
运用广搜统计每个点的深度
要想一颗树特殊，只有保证他的分支下面不再有子节点
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 1010 using namespace std; struct Edge
{
int u, v, cnt, next;
}edge[N * N]; int head[N], j, cnt;
int a[N];//记录各个点的深度
bool vis[N]; void Add(int u, int v)//邻接表
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt++;
} void Init()
{
memset(head, -, sizeof(head));
memset(a, , sizeof(a));
memset(vis, false, sizeof(vis));
cnt = j = ;
} void DFS(int u, int deep)
{
int v, i;
vis[u] = true;
for(i = head[u]; i != - ; i = edge[i].next)
{
v = edge[i].v;
if(!vis[v])
{
vis[v] = true;
DFS(v, deep + );
}
}
a[j++] = deep;
return ;
}//查找记录各个点的深度 int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
} int main()
{
int n, u, v;
while(~scanf("%d", &n))
{
Init();
for(int i = ; i < n ; i++)
{
scanf("%d%d", &u, &v);
Add(u, v);
Add(v, u);
}
DFS(, );
qsort(a, j, sizeof(a[]), cmp);
int deep = , f = , fl = ;
for(int i = ; i < j ; i++)
{
if(a[i - ] == a[i])
{
fl = ;//如果两个点的深度相同，就存在分支，即标记有分支
deep = a[i];
}
if(fl == && a[i] > deep)
f = ;//如果存在分支且分支的下面还有节点则输出NO
}
if(f == )
printf("YES\n");
else
printf("NO\n");
}
return ;
}