题解：P13266 [GCJ 2014 Finals] Symmetric Trees

BitByBit · 2025-09-01 18:53:52 · 题解

:::epigraph[——LA 群友] 做出来了=若至题 :::

思路

先看原题时限。120s,n=10^4,t=100，官方题解的 python \Theta(n^2) 都放过去了。但是良心的洛谷把时限砍到了 5s，必须考虑更优秀的做法。

树 hash

要快速判断子树是否同构，树 hash 是显然的。参考 https://oi-wiki.org/graph/tree-hash/ 的树 hash，钦定某个点为根，构造 hash 函数：

h(x)=\left( w_{c_x}+\sum_{y \in S} f(h(y)) \right)\mod 2^{64}

其中 h(x) 为以 x 为根的子树的 hash 值，c_x 表示 x 的颜色，w_c 表示对颜色 c 随机赋的权值。S 表示 x 的儿子组成的集合。f 为 xor shift，具体见代码：

ull xor_shift(ull x)
{
    x^=mask;x^=x<<13;x^=x>>7;x^=x<<17;x^=mask;
    return x;
}

mask 为随机生成的常数，能够避免出题人对着代码卡。

求 hash 的函数：

ull get_hash(int x,int f)
{
    Hash[x]=W[Col[x]];
    for(int y:G[x])
    {
        if(y==f)continue;
        Hash[x]+=xor_shift(get_hash(y,x));
    }
    return Hash[x];
}

判断是否对称

观察题目中的图片，发现对称轴有可能经过边中点或者是树上的一条链。为了方便，我们在每条边中点新建一个点，全部赋上一个不存在的颜色，可以省去很多分讨。

我们发现有根的时候是好做的，于是钦定对称轴上的一个点为根，有以下情况：

所有子树可以两两配对得到对称的局面；
除一棵子树外其他子树可以两两对称；
除两棵子树外其他子树可以两两对称；
有超过两棵子树无法匹配（这种情况下这棵树不是对称的）。

对无法匹配的子树进行 dfs，每棵子树有以下情况：

所有子树可以两两配对得到对称的局面；
除一棵子树外其他子树可以两两对称；
有超过一棵子树无法匹配（这种情况下这棵树不是对称的）。

其中第二种情况递归判断即可。

对于是否可以两两匹配，有两种方法，一个是把 hash 值全部丢到 map 里数一下个数的奇偶性，一个是把 hash 值异或起来，相同的会互相抵消。

检验代码：

bool check(int x,int f)
{
    int cnt=0;
    ull sum=0;
    for(int y:G[x])
    {
        if(y==f)continue;
        cnt++;
        sum^=Hash[y];
    }
    if(!(cnt&1))return bool(sum);
    for(int y:G[x])
        if(y!=f&&Hash[y]==sum)
            return check(y,x);
    return 1;
}
bool chin_check(int x)
{
    map<ull,bool>Mp;
    basic_string<ull>Key;
    for(int y:G[x])Mp[Hash[y]]^=1;
    for(auto i:Mp)if(i.se)Key+=i.fi;
    int cnt=Key.size();
    if(cnt==0)return 0;
    if(cnt>2)return 1;
    for(ull i:Key)
        for(int y:G[x])
            if(Hash[y]==i)
                if(check(y,x))
                    return 1;
    return 0;
}

现在我们已经可以枚举每个点并判断了，复杂度 \Omega(n^2)，应该已经够通过原题的 120s 时限了。

猜结论

现在瓶颈在于快速找对称轴上的点了。猜一个结论：树的重心一定在对称轴上。 :::info[证明] 设 T 的重心为 c。由树的重心性质，删除 c 后，每个子树的大小不超过 |T|/2。

假设 T 在某条轴 \ell 上对称。对称性要求：每个节点在轴两侧都有结构和颜色完全相同的镜像节点。

若 c \notin \ell，则 \ell 将 c 分割到一侧，使得两侧子树大小不同。即存在 S_1,S_2，使两子树左右对称但 |S_1|\ne |S_2|。这与对称要求矛盾，因为对称子树必须大小相等。

因此，重心 c 必在对称轴 \ell 上（或两个重心之间的中轴线上）。证毕。 ::: 所以找到重心后进行上述验证即可做到 \Theta(n\log n)，时限 5s 都嫌多了，我 100ms 就跑过去了。

找重心代码：

void get_centroid(int x,int f)
{
    Size[x]=1;
    Weight[x]=0;
    for(int y:G[x])
    {
        if(y==f)continue;
        get_centroid(y,x);
        Size[x]+=Size[y];
        Weight[x]=max(Weight[x],Size[y]);
    }
    Weight[x]=max(Weight[x],n-Size[x]);
    if(Weight[x]<=n>>1)C[C[0]?1:0]=x;
}

代码

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define lll __int128
#define db double
#define ld long double
#define fi first
#define se second
#define endl '\n'
#define ainl inline __attribute__((always_inline))
#define inf 0x3f3f3f3f
#define ninf 0xcfcfcfcf
#define infll 0x3f3f3f3f3f3f3f3f
#define ninfll 0xcfcfcfcfcfcfcfcf
#define start_mtest\
    int tcnt;\
    cin>>tcnt;\
    for(int tcase=1;tcase<=tcnt;tcase++)[&]()\
    {
#define end_mtest\
    }();
#define N 20010
int n,n0;
basic_string<int>G[N];
int C[2],Col[N],Size[N],Weight[N];
ull Hash[N],W[N];
random_device seed;
mt19937_64 rndll(seed());
const ull mask=rndll();
void get_centroid(int x,int f)
{
    Size[x]=1;
    Weight[x]=0;
    for(int y:G[x])
    {
        if(y==f)continue;
        get_centroid(y,x);
        Size[x]+=Size[y];
        Weight[x]=max(Weight[x],Size[y]);
    }
    Weight[x]=max(Weight[x],n-Size[x]);
    if(Weight[x]<=n>>1)C[C[0]?1:0]=x;
}
ull xor_shift(ull x)
{
    x^=mask;x^=x<<13;x^=x>>7;x^=x<<17;x^=mask;
    return x;
}
ull get_hash(int x,int f)
{
    Hash[x]=W[Col[x]];
    for(int y:G[x])
    {
        if(y==f)continue;
        Hash[x]+=xor_shift(get_hash(y,x));
    }
    return Hash[x];
}
bool check(int x,int f)
{
    int cnt=0;
    ull sum=0;
    for(int y:G[x])
    {
        if(y==f)continue;
        cnt++;
        sum^=Hash[y];
    }
    if(!(cnt&1))return bool(sum);
    for(int y:G[x])
        if(y!=f&&Hash[y]==sum)
            return check(y,x);
    return 1;
}
bool chin_check(int x)
{
    map<ull,bool>Mp;
    basic_string<ull>Key;
    for(int y:G[x])Mp[Hash[y]]^=1;
    for(auto i:Mp)if(i.se)Key+=i.fi;
    int cnt=Key.size();
    if(cnt==0)return 0;
    if(cnt>2)return 1;
    for(ull i:Key)
        for(int y:G[x])
            if(Hash[y]==i)
                if(check(y,x))
                    return 1;
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i=1;i<=27;i++)W[i]=rndll();
    start_mtest
    cin>>n0;
    for(int i=1;i<=n0<<1;i++)G[i].clear();
    for(int i=1;i<=n0;i++)
    {
        char x;
        cin>>x;
        Col[i]=x-64;
    }
    n=n0;
    for(int i=1;i<=n0-1;i++)
    {
        int x,y;
        cin>>x>>y;
        Col[++n]=27;
        G[x]+=n;
        G[n]+=x;
        G[y]+=n;
        G[n]+=y;
    }
    C[0]=C[1]=0;
    get_centroid(1,0);
    get_hash(C[0],0);
    cout<<"Case #"<<tcase<<": "<<(chin_check(C[0])?"NOT SYMMETRIC\n":"SYMMETRIC\n");
    end_mtest
    return 0;
}

:::