树同构简述

引入

树是一种常见的数据结构。
我们把$N$个点，$N-1$条边的联通无向图称为树。
对于两棵树$T_1和T_2$，如果能够把树$T_1$的所有点重新标号，使得树$T_1和T_2$完全相同，那么称这两棵树是同构的。也就是说，它们具有相同的形态。
下面介绍如何判断树同构。

解决树同构问题我们一般使用树哈希.哈希方式很简单，根据下面这个式子来算：

F i = 1 + ∑ v ∈ { s o n [ x ] } f [ v ] ∗ p r i m e [ s i z [ v ] ] F_i=1+\sum_{v\in\{son[x]\}}f[v]*prime[siz[v]] Fi​=1+v∈{
son[x]}∑​f[v]∗prime[siz[v]]

对于有根树，我们只需求出根节点的$hash$值然后比较即可.对于无根树的情况，我们可以把每个节点作为根的$hash$值求出，然后将结果相乘，看是否相同.如果有复杂度需求的话，可以考虑使用$upanddown$树$dp$，还可以将树的重心提取为根做$hash$.

例题

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

由于是无根树且$n$很小，所以这里我采用了对每个节点一一求$hash$的方法，最后结果用$map$存储.

复杂度$\mathcal{O}(m{n}^2)$

const ll prime[51]={ 
   0, 9999991, 9999973, 9999971, 9999943, 9999937, 9999931, 9999929, 9999907, 9999901, 9999889, 9999883, 9999877, 9999863, 9999823, 9999761, 9999749, 9999739, 9999713, 9999677, 9999667, 9999659, 9999653, 9999637, 9999601, 9999593, 9999533, 9999511, 9999481, 9999469, 9999463, 9999433, 9999419, 9999401, 9999397, 9999347, 9999337, 9999317, 9999299, 9999289, 9999277, 9999271, 9999233, 9999221, 9999217, 9999193, 9999167, 9999163, 9999161, 9999083, 9999071};
const ll N=51;

ll head[N], to[N<<1], next[N<<1], tot;
inline void add(ll x, ll y){ 
   
	to[++tot]=y; next[tot]=head[x]; head[x]=tot;
}
inline void Link(ll x, ll y){ 
   
	add(x, y); add(y, x);
}

ll siz[N];
inline ll dfs(ll x, ll fa){ 
   
	siz[x]=1;
	ll tmp=1;
	for (R ll i=head[x], ver; i; i=next[i]){ 
   
		ver=to[i];
		if (ver==fa) continue;
		ll rem=dfs(ver, x);
		(tmp+=rem*prime[siz[ver]])%=mod;
	}
	return tmp;
}

ll n, m;
map<ll, ll> mp;
ll cnt;

int main(){ 
   
	read(m);
	while (m--){ 
   
		tot=0;
		memset(head, 0, sizeof head);
		++cnt;
		read(n);
		for (R ll i=1, x; i<=n; i++){ 
   
			read(x);
			if (x) Link(x, i);
		}
		ll tmp=1;
		for (R ll i=1; i<=n; i++) (tmp*=dfs(i, 0))%=mod;
		if (mp.find(tmp)==mp.end()) writeln(mp[tmp]=cnt);
		else writeln(mp[tmp]);
	}
}

[JSOI2016]独特的树叶

这题我们先用二次扫描换根法求出第一棵树上每个节点的$hash$值，然后将其存进平衡树里面($set$或$map$均可)，接下来对第二棵树进行$\mathcal{D}\mathcal{P}$,然后枚举每一叶子节点，推出其父节点删去该叶后的$hash$值，然后在平衡树中查询是否存在该值，若存在，则该叶删去即可.

const ll N=2e5+5;

ll head[N], to[N<<1], next[N<<1], tot; 
inline void add(ll x, ll y){ 
   
	to[++tot]=y; next[tot]=head[x]; head[x]=tot;
}
inline void Link(ll x, ll y){ 
   
	add(x, y); add(y, x);
}

ll n;

ll prime[N*10], sum;
bool book[N*10];
inline void mlg_solve(ll lim){ 
   
	for (R ll i=2; i<=lim; i++){ 
   
		if (book[i]) continue;
		prime[++sum]=i;
		for (R ll j=i; j<=lim; j+=i) book[j]=true;
	}
}

ll g[N], siz[N];
inline void dfs1(ll x, ll fa){ 
   
	g[x]=1; siz[x]=1;
	for (R ll i=head[x], ver; i; i=next[i]){ 
   
		ver=to[i];
		if (ver==fa) continue;
		dfs1(ver, x);
		siz[x]+=siz[ver];
		(g[x]+=prime[siz[ver]]*g[ver])%=mod;
	}
}

ll res[N];
inline void dfs2(ll x, ll fa){ 
   
	res[x]=g[x];
	for (R ll i=head[x], ver; i; i=next[i]){ 
   
		ver=to[i];
		if (ver==fa) continue;
		ll tmp=g[ver];
		(((g[x]-=tmp*prime[siz[ver]])%=mod)+=mod)%=mod;
		(g[ver]+=g[x]*prime[n-siz[ver]])%=mod;
		dfs2(ver, x);
		(g[x]+=prime[siz[ver]]*tmp)%=mod;
	}
}

multiset<ll> st;

ll deg[N];
ll f[N];
int main(){ 
   
	mlg_solve(2000000);
	read(n);
	for (R ll i=1, x, y; i<n; i++){ 
   
		read(x); read(y);
		Link(x, y);
	}
	dfs1(1, 0); dfs2(1, 0);
	for (R ll i=1; i<=n; i++) st.insert(res[i]);
	++n;
	tot=0;
	memset(head, 0, sizeof head);
	for (R ll i=1, x, y; i<n; i++){ 
   
		read(x); read(y);
		Link(x, y);
		++deg[x]; ++deg[y];
		f[x]=y; f[y]=x;
	}
	dfs1(1, 0); dfs2(1, 0);
	for (R ll i=1; i<=n; i++)
		if (deg[i]==1){ 
   
			ll tmp=((res[f[i]]-prime[1])%mod+mod)%mod;
			if (*st.lower_bound(tmp)==tmp) return writeln(i), 0;
		}
}