CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:树同构 [2020/08/14 22:51]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:树同构 [2020/08/16 11:05] (当前版本)
jxm2001
@@ 行 38: / 行 38: @@
 	head[u]=edge_cnt;
 }
-int sz2[MAXN],mson[MAXN],tot_sz,root_sz;
+int sz[MAXN],mson[MAXN],tot_sz,root_sz;
+int h1[MAXN],h2[MAXN];
+vector<int> rt;
+vector<pair<int,int> >root[MAXN];
 void find_root(int u,int fa){
-	sz2[u]=1;mson[u]=0;
+	sz[u]=1;mson[u]=0;
 	for(int i=head[u];i;i=edge[i].next){
 		int v=edge[i].to;
@@ 行 46: / 行 49: @@
 		continue;
 		find_root(v,u);
-		sz2[u]+=sz2[v];
+		sz[u]+=sz[v];
-		mson[u]=max(mson[u],sz2[v]);
+		mson[u]=max(mson[u],sz[v]);
 	}
-	mson[u]=max(mson[u],tot_sz-sz2[u]);
+	mson[u]=max(mson[u],tot_sz-sz[u]);
 	if(mson[u]<root_sz)
 	root_sz=mson[u];
 }
-int sz[MAXN],h1[MAXN],h2[MAXN];
 void Hash(int u,int fa){
 	sz[u]=1,h1[u]=h2[u]=0;
@@ 行 67: / 行 69: @@
 	h2[u]=(1LL*h2[u]*sz[u]+sz[u])%Mod;
 }
-vector<pair<int,int> >root[MAXN];
 bool cmp(int a,int b){
 	if(root[a].size()!=root[b].size())
@@ 行 91: / 行 92: @@
 		_rep(i,1,n){
 			p=read_int();
-			if(p){
+			if(p)Insert(p,i),Insert(i,p);
-				Insert(p,i);
-				Insert(i,p);
-			}
 		}
+		rt.clear();
 		tot_sz=root_sz=n;
 		find_root(1,0);
 		_rep(i,1,n){
-			if(mson[i]==root_sz){
+			if(mson[i]==root_sz)
-				Hash(i,0);
+			rt.push_back(i);
-				root[k].push_back(make_pair(h1[i],h2[i]));
+		}
-			}
+		_for(i,0,rt.size()){
+			Hash(rt[i],0);
+			root[k].push_back(make_pair(h1[rt[i]],h2[rt[i]]));
 		}
 		_rep(i,1,k){
@@ 行 117: / 行 118: @@
 ===== 最小表示法 =====
+==== 算法简介 ====
+利用每棵树的最小字典序的括号序列判断树同构。
+==== 算法思想 ====
+易知两棵树同构等价于两棵树最小字典序的括号序列相同。当然实现的时候不需要真正模拟括号序列，可以考虑使用 $01$ 串。
+于是考虑如何快速求出每棵树的最小表示法。
+一个比较暴力的算法是先求出所有子树的最小表示法，然后用 $\text{Trie}$ 树实现 $O(n)$ 排序，然后顺次拼接，最后最外层添加括号。
+上述算法的时间复杂度为 $O(n^2)$，考虑优化算法。
+发现可以用名次代替括号序列。考虑根据对所有同一深度的树排序，每个深度为 $d$ 的结点的序列由深度为 $d+1$ 的儿子结点的名次构成。
+注意名次是指在两棵树中所有深度为 $d+1$ 的结点中的名次，初始叶子结点名次均为 $0$。
+然后对所有深度为 $d$ 的结点的序列再次排序，如果使用基数排序，可以使得总时间复杂度为 $O(n)$。<del>但是树哈希太香了</del>
 ===== 算法练习 =====
+==== 习题一 ====
+[[https://www.luogu.com.cn/problem/P4323|洛谷p4323]]
+=== 题意 ===
+给定两棵带标号无根树，保证其中一棵树删去一个结点后可以与另一棵树同构。
+问需要删去哪个结点才能使两棵树同构，如果有多个满足条件的结点，输出编号最小的。
+=== 题解 ===
+对结点数较少的树，考虑换根 $\text{dp}$ 枚举以每个点为根的情况同时将哈希值存入 $\text{set}$。
+对结点数较多的树，考虑换根 $\text{dp}$ 枚举以每个点为根的情况，如果该结点度为一，则在 $\text{set}$ 中查找是否存在与该结点相连结点的哈希值。
+时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,Mod=1e9+7;
+const int MAXP=14e5;
+bool vis[MAXP];
+int prime[MAXP],cnt;
+void Prime(){
+	vis[1]=true;
+	_for(i,2,MAXP){
+		if(!vis[i])prime[cnt++]=i;
+		for(int j=0;j<cnt&&i*prime[j]<MAXP;j++){
+			vis[i*prime[j]]=true;
+			if(i%prime[j]==0) break;
+		}
+	}
+}
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int sz[MAXN],h1[MAXN],h2[MAXN],deg[MAXN],ans;
+set<pair<int,int> >s;
+void Hash(int u,int fa){
+	sz[u]=1,h1[u]=h2[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		Hash(v,u);
+		sz[u]+=sz[v];
+		h1[u]=(h1[u]+1LL*h1[v]*sz[v])%Mod;
+		h2[u]=(h2[u]+1LL*h2[v]*prime[sz[v]])%Mod;
+	}
+	h1[u]=(h1[u]+sz[u])%Mod;
+	h2[u]=(h2[u]+prime[sz[u]])%Mod;
+}
+void update(int u,int v){
+	h1[u]=(h1[u]-sz[v]-1LL*h1[v]*sz[v])%Mod;
+	h1[u]=(h1[u]+Mod)%Mod;
+	h2[u]=(h2[u]-prime[sz[u]]-1LL*h2[v]*prime[sz[v]]+prime[sz[u]-sz[v]])%Mod;
+	h2[u]=(h2[u]+Mod)%Mod;
+	sz[u]-=sz[v];
+	h1[v]=(h1[v]+1LL*h1[u]*sz[u]+sz[u])%Mod;
+	h2[v]=(h2[v]+1LL*h2[u]*prime[sz[u]]+prime[sz[v]+sz[u]]-prime[sz[v]])%Mod;
+	sz[v]+=sz[u];
+}
+void dfs(int u,int fa){
+	s.insert(make_pair(h1[u],h2[u]));
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		update(u,v);
+		dfs(v,u);
+		update(v,u);
+	}
+}
+void dfs2(int u,int fa){
+	if(deg[u]==1){
+		int v=edge[head[u]].to;
+		if(s.count(make_pair(h1[v],h2[v])))
+		ans=min(u,ans);
+	}
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		update(u,v);
+		dfs2(v,u);
+		update(v,u);
+	}
+}
+int main()
+{
+	Prime();
+	int n=read_int(),u,v;
+	_for(i,1,n){
+		u=read_int(),v=read_int();
+		Insert(u,v);Insert(v,u);
+	}
+	Hash(1,0);
+	dfs(1,0);
+	edge_cnt=0;
+	_rep(i,1,n)head[i]=0;
+	ans=n+1;
+	_rep(i,1,n){
+		u=read_int(),v=read_int();
+		Insert(u,v);Insert(v,u);
+		deg[u]++;deg[v]++;
+	}
+	Hash(1,0);
+	dfs2(1,0);
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+==== 习题二 ====
+[[https://ac.nowcoder.com/acm/contest/5675/J|牛客暑期多校(第十场) J 题]]
+=== 题意 ===
+给定两棵带标号有根树，保证同构。要求修改两棵树的标号，将两棵树变成完全相同的树，问最小修改次数。
+=== 题解 ===
+先树哈希求出每棵子树的哈希值，再考虑 $\text{dp}$，定义 $\text{dp}(u_1,u_2)$ 为将以 $u1,u2$ 为根的两棵树匹配时最多的标号相同的位置个数。
+对两棵同构的树，暴力考虑枚举所有儿子结点。将所有的同构的儿子 $v1,v2$ 结点连上一条权值为 $\text{dp}(v_1,v_2)$ 的边，然后跑最大二分图匹配。
+注意如果根节点标号相同需要将最大匹配结果加一。
+最终答案为 $n-\text{dp}(\text{root}_1,\text{root}_2)$，时间复杂度 $O\left(\sum (\text{son}^2+\text{son}^3)\right)=O(n^3)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1005,Mod=1e9+7;
+namespace KM{
+	const int MAXN=505,Inf=1e9;
+	int n,w[MAXN][MAXN],lx[MAXN],ly[MAXN],lack[MAXN],p[MAXN];
+	int linkx[MAXN],linky[MAXN],visx[MAXN],visy[MAXN];
+	void init(int _n){
+		n=_n;
+		_rep(i,1,n)
+		ly[i]=linkx[i]=linky[i]=visx[i]=visy[i]=0;
+		_rep(i,1,n)
+		_rep(j,1,n)
+		w[i][j]=0;
+	}
+	void augment(int pos){
+		int temp;
+		while(pos){
+			temp=linkx[p[pos]];
+			linkx[p[pos]]=pos;
+			linky[pos]=p[pos];
+			pos=temp;
+		}
+	}
+	void bfs(int s,int k){
+		queue<int>q;
+		_rep(i,1,n)
+		lack[i]=Inf;
+		q.push(s);
+		while(true){
+			while(!q.empty()){
+				int u=q.front();q.pop();
+				visx[u]=k;
+				_rep(v,1,n){
+					if(visy[v]==k)
+					continue;
+					if(lx[u]+ly[v]-w[u][v]<lack[v]){
+						lack[v]=lx[u]+ly[v]-w[u][v];p[v]=u;
+						if(!lack[v]){
+							visy[v]=k;
+							if(!linky[v])
+							return augment(v);
+							else
+							q.push(linky[v]);
+						}
+					}
+				}
+			}
+			int a=Inf;
+			_rep(i,1,n) if(visy[i]!=k)
+			a=min(a,lack[i]);
+			_rep(i,1,n){
+				if(visx[i]==k)lx[i]-=a;
+				if(visy[i]==k)ly[i]+=a;
+				else lack[i]-=a;
+			}
+			_rep(i,1,n){
+				if(visy[i]!=k&&!lack[i]){
+					visy[i]=k;
+					if(!linky[i])
+					return augment(i);
+					else
+					q.push(linky[i]);
+				}
+			}
+		}
+	}
+	int get_pair(){
+		int k=0;
+		_rep(i,1,n){
+			lx[i]=-Inf;
+			_rep(j,1,n)
+			lx[i]=max(lx[i],w[i][j]);
+		}
+		_rep(i,1,n)
+		bfs(i,i);
+		int ans=0;
+		_rep(i,1,n)
+		ans+=w[linky[i]][i];
+		return ans;
+	}
+}
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int n,head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int root[2],sz[MAXN];
+int h1[MAXN],h2[MAXN],dp[MAXN][MAXN];
+void Hash(int u){
+	sz[u]=1,h1[u]=h2[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		Hash(v);
+		sz[u]+=sz[v];
+		h1[u]=(h1[u]+1LL*h1[v]*sz[v])%Mod;
+		h2[u]=(h2[u]+1LL*h2[v]*sz[v])%Mod;
+	}
+	h1[u]=(h1[u]+sz[u])%Mod;
+	h2[u]=(1LL*h2[u]*sz[u]+sz[u])%Mod;
+}
+bool cmp(int a,int b){return (h1[a]==h1[b])&&(h2[a]==h2[b]);}
+void dfs(int u1,int u2){
+	if(~dp[u1][u2])return;
+	int cnt=0;
+	for(int i=head[u1];i;i=edge[i].next){
+		int v1=edge[i].to;
+		for(int j=head[u2];j;j=edge[j].next){
+			int v2=edge[j].to;
+			if(cmp(v1,v2))dfs(v1,v2);
+		}
+		cnt++;
+	}
+	KM::init(cnt);
+	for(int i=head[u1],pos1=1;i;i=edge[i].next,pos1++){
+		int v1=edge[i].to;
+		for(int j=head[u2],pos2=1;j;j=edge[j].next,pos2++){
+			int v2=edge[j].to;
+			if(cmp(v1,v2))
+			KM::w[pos1][pos2]=dp[v1][v2];
+		}
+	}
+	dp[u1][u2]=KM::get_pair()+((u1+n)==u2);
+}
+int main()
+{
+	n=read_int();
+	_rep(i,1,n){
+		int p=read_int();
+		if(p)Insert(p,i);
+		else root[0]=i;
+	}
+	Hash(root[0]);
+	_rep(i,1,n){
+		int p=read_int()+n;
+		if(p!=n)Insert(p,i+n);
+		else root[1]=i+n;
+	}
+	Hash(root[1]);
+	mem(dp,-1);
+	dfs(root[0],root[1]);
+	enter(n-dp[root[0]][root[1]]);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具