P5043 【模板】树同构（[BJOI2015]树的同构）

题目

分析

树哈希模板题。

这里介绍一种不容易被卡的树哈希。

判断树同构有两种办法，一种是最小表示法，一种就是树哈希。

树哈希有很多办法，但是大多很容易被卡掉，这里介绍一种。

同样的，树哈希是可以换根dp的，也就是说可以求出每一个点作为根的答案。

如果我们需要快速判断，那么我们可以考虑重心来判断，最多四个重心，一共也四种情况，只要一个满足则说明两个树同构。

代码

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
	while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template <typename T>
inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
#define ll long long
#define PII pair<int,int>
#define mp make_pair
#define fi first
#define se second
const int N=1e5+5,M=1e6+5;
int n,m,p,prime[N],cnt,siz[N],f[N],g[N],rt,Ans[N];
vector<int>vec[N];
bool vis[M];
void Primes(int n){
	for(int i=2;i<=n;i++){
		if(!vis[i]) prime[++cnt]=i;
		for(int j=1;i*prime[j]<=n&&j<=cnt;j++){
			vis[i*prime[j]]=true;
			if(i%prime[j]==0) break;
		}
	}
	return ;
}
void dfs1(int x){
	f[x]=1;siz[x]=1;
	for(auto y:vec[x]){dfs1(y);siz[x]+=siz[y];f[x]+=f[y]*prime[siz[y]];}
	return ;
}
void dfs2(int x,int val){
	val=val*prime[n-siz[x]];
	g[x]=f[x]+val;
	for(auto y:vec[x]) dfs2(y,val+f[x]-f[y]*prime[siz[y]]);
	return ;
}
int now=n,rt1=51,rt2=51;
void GetRoot(int x){
	int Maxn=0;
	for(auto y:vec[x]){
		GetRoot(y);
		Maxn=max(Maxn,siz[y]);
	}
	Maxn=max(Maxn,n-siz[x]);
	if(Maxn<now) now=Maxn,rt1=x,rt2=51;
	else if(Maxn==now) rt2=x;
	return ;
}
PII v[N];
int main(){
	read(m);Primes(1000);
	for(int i=1;i<=m;i++){
		read(n);
		for(int i=1;i<=n;i++) vec[i].clear();
		for(int i=1,x;i<=n;i++){read(x),vec[x].push_back(i);if(x==0) rt=i;}
		dfs1(rt);dfs2(rt,0);
		rt1=rt2=51,now=n;
		GetRoot(rt);
		v[i]=mp(g[rt1],g[rt2]);
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if(v[i].se&&v[j].se){if(v[i].fi==v[j].fi||v[i].fi==v[j].se||v[i].se==v[j].fi||v[i].se==v[j].se){Ans[i]=j;break;}}
			else if(v[i].se){if(v[i].fi==v[j].fi||v[i].se==v[j].fi){Ans[i]=j;break;}}
			else if(v[j].se){if(v[i].fi==v[j].fi||v[i].fi==v[j].se){Ans[i]=j;break;}}
			else{if(v[i].fi==v[j].fi){Ans[i]=j;break;}}
		}
		write(Ans[i]),putchar('
');
	}
	
	return 0;
}