题解：CF1800G Symmetree

~~这真的是紫？~~

通过对称想到同构，同构又能想到树哈希，对称肯定是需要递归的，那么对于当前递归到的一个点

x

，根据

x

的儿子数量分类讨论，如果

x

的儿子数量是偶数，那么搞一个 map 记录分别以

x

的所有儿子为根的子树的哈希值，然后用迭代器遍历一遍 map，看一下对于每一个哈希值的次数是否为偶数，如果有一个哈希值的次数不是偶数，那么此树显然不对称，当

x

的儿子数量为奇数，也是差不多的情况，只是哈希值的次数不是偶数的哈希值数量不能超过

1

，和偶数的情况（不能超过

0

）略有不同，然后其实这两个情况是可以合并的，可以直接用

x

的儿子数量为奇数的情况，因为是不可能存在

x

的儿子数量为偶数但存在一个哈希值的次数是奇数的（根据偶数加偶数等于偶数，偶数加奇数等于奇数，奇数加奇数等于偶数的道理）。

当然，如果这样，那还递归个毛线？直接判断

1

的儿子数量，跑一遍不就行了？实则不然，当

x

的儿子数量为奇数时，对于那唯一一个哈希值次数不是偶数的哈希值，其实是需要继续递归的，因为它落单了。

注意：那唯一的一个哈希值，我们是需要找到所有儿子的哈希值是这个的儿子都要递归一遍，因为分不清哪个是落单的。

多测不清空，爆零两行泪！

时间复杂度

O(\sum n)

。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
vector<int>e[N];
int h[N];
int son[N];
mt19937 r(time(0));
int rr = r();
int s(int x)
{
    x^=rr;
    x^=(x<<13);
    x^=(x>>7);
    x^=(x<<17);
    x^=rr;
    return x;
}
int dfs(int x,int fa)
{
    h[x] = 1;
    for(int v:e[x])
    {
        if(v!=fa)
        {
            h[x]+=s(dfs(v,x));
        }
    }
    return h[x];
}
int flag;
void dfs1(int x,int fa)
{
    if(!flag)
    {
        return;
    }
    int cnt = 0;
    map<int,int>mp;
    for(int v:e[x])
    {
        if(v!=fa)
        {
            son[++cnt] = v;
            mp[h[v]]++;
        }
    }
    int ans = 0,num = 0;
    for(auto it = mp.begin();it!=mp.end();it++)
    {
        ans+=(it->second&1);
        if(it->second&1)
        {
            num = it->first;
        }
    }
    if(ans>1)
    {
        flag = 0;
        return;
    }
    if(ans == 1)
    {
        for(int i = 1;i<=cnt;i++)
        {
            if(h[son[i]] == num)
            {
                dfs1(son[i],x);
            }
        }
    }
}
signed main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        int n;
        scanf("%d",&n);
        for(int i = 1;i<=n;i++)
        {
            e[i].clear();
        }
        flag = 1;
        for(int i = 1;i<n;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            e[x].push_back(y);
            e[y].push_back(x);
        }
        int g = dfs(1,0);
        dfs1(1,0);
        if(flag)
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
    }
    return 0;
}

题解：CF1800G Symmetree

文章操作

相关推荐

评论

题解：CF1800G Symmetree