题解：P13266 [GCJ 2014 Finals] Symmetric Trees
dyc2022
·
·
题解
更好的阅读体验
NOIP2025 RP++ 喵。
考虑哈希。
假设 c_i 为节点 i 的颜色。
首先为了避免冲突，我们将 c_i 映射成随机大整数。然后我们构造一个哈希函数，既能体现出树的形态，又能体现点的颜色。可以这样：
\operatorname{hash}(u) = c_u + \sum_{v \isin \operatorname{son}_u} \operatorname{shift}(\operatorname{hash}(v))
接下来无非就两种情况：对称中心是点，对称中心是边。
- 如果对称中心是点，那么这个点 $u$ 的子树一定可以两两配对，直到剩下零个或一个或两个子树。
- 我们想到一个看起来很聪明的方法：记录一个点所有子树哈希值的 $\operatorname{xor}$。
- 如果最后剩下 $0$ 个子树，那么异或值为 $0$，相当好判断。
- 如果最后剩下 $1$ 个子树，那么异或值就是剩下的一个子树的哈希值。需要满足这个子树本身是对称的。在实现中可以开一个类似 `map` 的数据结构来存。
- 如果最后剩下 $2$ 个子树，看起来不太好处理。但是仔细想一下，如果真的剩下两个对称的子树，我们可以把对称中心沿着其中一棵子树往下跳，直到跳到分岔的地方。这个时候就变成了剩下 $1$ 个子树的情况。所以不需要特别处理这种情况。
- 如果对称中心是边，那很简单，只要看边两端的哈希值是否相等就可以了。
至此可以做到 $O(n^2)$：枚举对称中心，每次重新计算哈希值。
但是还不够。
考虑换根 dp。我们考虑 $f_u$ 表示钦定 $1$ 为根，$u$ 子树的哈希值，$g_u$ 表示钦定 $u$ 为根，整棵树的哈希值。
$f$ 是好求的。假设 $fa_u$ 表示 $u$ 的父亲，那么我们把 $g$ 从 $fa_u$ 转移到 $u$，需要在继承之前 $f_u$ 的信息的基础上，加入 $fa_u$ 所在子树的信息。
由于我们之前是求和计算哈希值，所以父亲的哈希值是很好算的，直接拿 $g_{fa_u}$ 减去 $f_u$ 即可。
但是上面的讨论中，我们还要把所有对称的子树抠出来扔到 `map` 里面，所以我们还要同时记录一棵子树是否合法。判断一个大子树抠掉一个小子树是否合法也是容易的。
然后就变成基础的换根了。我们可以全局维护一下每个点邻居的异或值，还有每个点周围对称子树的 `map`。我在实现中其实用了 `unordered_map`，这样可以认为是线性的。
这道题就做完了，复杂度 $O(n)$。
```cpp
#include<bits/stdc++.h>
#define endl '\n'
#define N 10006
using namespace std;
using ull=unsigned long long;
mt19937_64 rnd(time(0));
struct Node{ull has; int o;} f[N],g[N];
ull refer[206],a[N],xor_sum[N];
int n,ok; char ch[3];
vector<int> G[N];
unordered_map<ull,int> mp[N];
inline ull shift(ull x)
{
x^=x<<13,x^=x>>17,x^=x<<5;
return x;
}
int check(int u,ull cut)
{
ull new_xor=xor_sum[u]^cut;
int new_cnt=mp[u][new_xor]-(new_xor==cut);
if(!new_xor||new_cnt)return 1;
return 0;
}
void dfs1(int u,int fa)
{
f[u].has=a[u];
for(int v:G[u])if(v!=fa)
dfs1(v,u),f[u].has+=shift(f[v].has);
unordered_map<ull,int> mp; ull xor_sum=0;
for(int v:G[u])if(v!=fa&&f[v].o)mp[f[v].has]++;
for(int v:G[u])if(v!=fa)xor_sum^=f[v].has;
if(!xor_sum||mp[xor_sum])f[u].o=1;
else f[u].o=0;
}
void dfs2(int u,int fa)
{
if(fa)
{
Node hf; hf.has=g[fa].has-shift(f[u].has);
if(hf.has==f[u].has)ok=1;
hf.o=check(fa,f[u].has),g[u].has=a[u];
for(int v:G[u])
{
Node now=(v==fa?hf:f[v]); g[u].has+=shift(now.has);
if(now.o)mp[u][now.has]++;
xor_sum[u]^=now.has;
}
g[u].o=check(u,0);
if(g[u].o)ok=2;
} else for(int v:G[u]) {
if(f[v].o)mp[u][f[v].has]++;
xor_sum[u]^=f[v].has;
}
for(int v:G[u])if(v!=fa)dfs2(v,u);
}
void solve(int _)
{
scanf("%d",&n),ok=0; if(_==17)cerr<<n<<endl;
for(int i='A';i<='Z';i++)refer[i]=rnd();
for(int i=1;i<=n;i++)
scanf("%s",ch+1),a[i]=refer[ch[1]],G[i].clear(),mp[i].clear(),xor_sum[i]=0;
for(int i=1,u,v;i<n;i++)
scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
dfs1(1,0),g[1]=f[1],dfs2(1,0);
printf("Case #%d: ",_);
printf(ok?"SYMMETRIC\n":"NOT SYMMETRIC\n");
}
main()
{
int T,_=0; scanf("%d",&T);
while(T--)solve(++_);
return 0;
}
```