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;

}