专栏文章

题解：P13266 [GCJ 2014 Finals] Symmetric Trees

BBitByBit
P13266题解参与者 5已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mio1hdqw
此快照首次捕获于
2025/12/02 11:49
3 个月前
此快照最后确认于
2025/12/02 11:49
3 个月前
查看原文
做出来了=若至题
——LA 群友

思路

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

树 hash

要快速判断子树是否同构，树 hash 是显然的。参考 https://oi-wiki.org/graph/tree-hash/ 的树 hash，钦定某个点为根，构造 hash 函数：
h(x)=(wcx+∑y∈Sf(h(y)))mod  264h(x)=\left( w_{c_x}+\sum_{y \in S} f(h(y)) \right)\mod 2^{64}
其中 h(x)h(x) 为以 xx 为根的子树的 hash 值，cxc_x 表示 xx 的颜色，wcw_c 表示对颜色 cc 随机赋的权值。SS 表示 xx 的儿子组成的集合。ff 为 xor shift，具体见代码：
CPP
ull xor_shift(ull x)
{
	x^=mask;x^=x<<13;x^=x>>7;x^=x<<17;x^=mask;
	return x;
}
mask 为随机生成的常数，能够避免出题人对着代码卡。
求 hash 的函数：
CPP
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 值异或起来，相同的会互相抵消。
检验代码：
CPP
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;
}
现在我们已经可以枚举每个点并判断了，复杂度 Ω(n2)\Omega(n^2)，应该已经够通过原题的 120s120s 时限了。

猜结论

现在瓶颈在于快速找对称轴上的点了。猜一个结论：树的重心一定在对称轴上。
证明
设 TT 的重心为 cc。由树的重心性质，删除 cc 后，每个子树的大小不超过 ∣T∣/2|T|/2。
假设 TT 在某条轴 ℓ\ell 上对称。对称性要求： 每个节点在轴两侧都有结构和颜色完全相同的镜像节点。
若 c∉ℓc \notin \ell，则 ℓ\ell 将 cc 分割到一侧，使得两侧子树大小不同。即存在 S1,S2S_1,S_2，使两子树左右对称但 ∣S1∣≠∣S2∣|S_1|\ne |S_2|。这与对称要求矛盾，因为对称子树必须大小相等。
因此，重心 cc 必在对称轴 ℓ\ell 上（或两个重心之间的中轴线上）。证毕。
所以找到重心后进行上述验证即可做到 Θ(nlog⁡n)\Theta(n\log n)，时限 5s5s 都嫌多了，我 100ms 就跑过去了。
找重心代码：
CPP
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;
}

代码

代码CPP
#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;
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...