Rikka with Tree
题意：给出树的定义，给出树相似的定义和不同的定义，然后给出一棵树，求是否存在一颗树即和其相似又与其不同。存在输出NO，不存在输出YES。
思路：以1号节点为根节点，我们观察到一颗树如果不存在这种树即与其相似又与其不同，那么这棵树要么所有节点的深度都不一样，要么有深度一样的并且他们的父节点都一样，后来想想，如果当前节点的父节点有多个儿子，那么当前节点则不能有儿子节点，否则就可以将儿子节点转移到兄弟节点上。思路很正确，比赛的时候用深搜递归写就错了，改成两层循环枚举任意两个节点看是否符合情况然后就过了，，过了。。代码能力还是不行啊，思路都一样，哪里写错了都不知道。
来看两种写法：
深搜标记：WA？
void init()
{
memset(d,0,sizeof(d));
memset(vis1,0,sizeof(vis1));
memset(vis2,0,sizeof(vis2));
for(int i=0;i<N;i++) g[i].clear();
}
void dfs(int u,int fa)
{
d[u]=d[fa]+1;
if(vis1[d[u]])
{
if(vis1[d[u]]!=fa)//度相同根节点不同那么可以互换
{f=1;
// printf("%d %d %d %d\n",u,fa,d[u],vis1[d[u]]);
}
}
else vis1[d[u]]=fa;
int len=g[u].size();
if(len>1) vis2[u]=1;
for(int i=0;i<len;i++)
{
int v=g[u][i];
if(v!=fa)
{
// printf("%d %d %d %d %d\n",v,u,fa,d[u],vis1[d[u]]);
if(u!=fa&&vis2[fa]) f=1;
dfs(v,u);
}
}
}
int main()
{
int n,u,v;
while(~scanf("%d",&n))
{
init();
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
f=0;
dfs(1,1);
if(f) puts("NO");
else puts("YES");
}
return 0;
}
以上有种样例能debug：
5
1 2
2 3
3 4
3 5
output: NO
Answer : YES
深搜预处理+枚举，AC！正确思路：父节点一样的情况下不能有儿子节点，否则可以将儿子节点转移至兄弟节点。
void init()
{
memset(pre,0,sizeof(pre));
memset(d,0,sizeof(d));
memset(vis1,0,sizeof(vis1));
memset(vis2,0,sizeof(vis2));
for(int i=0; i<N; i++) g[i].clear();
}
void dfs(int u,int fa)
{
d[u]=d[fa]+1;
pre[u]=fa;
int len=g[u].size();
for(int i=0; i<len; i++)
{
int v=g[u][i];
if(v!=fa) dfs(v,u);
}
}
int main()
{
int n,u,v;
while(~scanf("%d",&n))
{
init();
for(int i=1; i<n; i++)
{
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
f=0;
dfs(1,1);
for(int i=1; i<=n&&!f; i++)
for(int j=1; j<=n&&!f; j++)
if(i!=j&&d[i]==d[j])
{
if(pre[i]==pre[j])
{
int k1=g[i].size();
int k2=g[i].size();
if(k1>1||k2>1) f=1;
}
else f=1;
}
if(f) puts("NO");
else puts("YES");
}
return 0;
}