题意：众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：
对于一棵树TT,令F(T,i)F(T,i)为点1到点ii的最短距离（边长是1）.
两棵树AA和BB是相似的当且仅当他们顶点数相同且对于任意的ii都有F(A,i)=F(B,i)F(A,i)=F(B,i).
两棵树AA和BB是不同的当且仅当他们定点数不同或者存在一个ii使得以1号点为根的时候ii在两棵树中的父亲不同。
一棵树AA是特殊的当且仅当不存在一棵和它不同的树和它相似。
现在勇太想知道一棵树到底是不是特殊的。
当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？
画画图找下规律就行了。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+4;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct Edge {
int to,next;
Edge(){}
Edge(int _to,int _next):to(_to),next(_next){}
}e[MAXN<<1];
int head[MAXN],tot;
void init(){
memset(head,-1,sizeof(head));
tot=0;
}
void AddEdge(int u,int v){
e[tot]=Edge(v,head[u]);
head[u]=tot++;
e[tot]=Edge(u,head[v]);
head[v]=tot++;
}
int dep[MAXN],cnt[MAXN];
void dfs(int u,int fa,int d){
dep[u]=d;
++cnt[d];
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(v!=fa){
dfs(v,u,d+1);
}
}
}
int main()
{
int n;
while(~scanf("%d",&n)){
init();
for(int i=0,x,y;i<n-1;i++){
scanf("%d%d",&x,&y);
AddEdge(x,y);
}
memset(cnt,0,sizeof(cnt));
dfs(1,1,0);
int t=0;
while(cnt[t]==1)++t;
--t;
LL tx=cnt[t+1];
int flag=0;
for(int i=t+1;i<n;i++){
if(cnt[i]==0)break;
if(cnt[i]<tx){
flag=1;break;
}
tx=tx*2;
}
if(flag)puts("NO");
else puts("YES");
}
return 0;
}
|
