题目链接：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): 321 Accepted Submission(s): 162
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?
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
.
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
2 3
4
1 2
2 3
1 4
2 3
1 4
Sample Output
YES
NO
此题满足条件的只有一种情况，即： 树从上到下的结点数依次为： 1， 1， 1， ，，，，x（x为任意）. 也即是说，只有最后一层的结点数才能大于 1 .
dfs 求出每层的结点数， 就能判断出答案。
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std; bool ok;
vector<int> a[];
int num[]; void dfs(int u, int fa, int d)
{
num[d]++;
int len = a[u].size();
for(int i=; i<len; i++)
{
if(a[u][i]==fa) continue;
dfs(a[u][i], u, d+);
}
} int main()
{
int n;
while(~scanf("%d", &n))
{
for(int i=; i<; i++)
a[i].clear();
memset(num, , sizeof(num));
for(int i=; i<n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
}
ok = false;
dfs(, -, );
for(int i=; i<; i++)
{
if(num[i-]>&&num[i])
ok = true;
}
if(ok) printf("NO\n");
else printf("YES\n");
}
return ;
}