CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:树同构 [2020/08/15 15:23]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:树同构 [2020/08/16 11:05] (当前版本)
jxm2001
@@ 行 133: / 行 133: @@
 上述算法的时间复杂度为 $O(n^2)$，考虑优化算法。
-发现可以用名次代替括号序列。考虑根据深度化为树，每个深度为 $d$ 的结点的名次序列由深度为 $d+1$ 的结点的名次构成。
+发现可以用名次代替括号序列。考虑根据对所有同一深度的树排序，每个深度为 $d$ 的结点的序列由深度为 $d+1$ 的儿子结点的名次构成。
 注意名次是指在两棵树中所有深度为 $d+1$ 的结点中的名次，初始叶子结点名次均为 $0$。
-然后对所有深度为 $d$ 的结点的名次序列再次排序，如果使用基数排序，可以使得总时间复杂度为 $O(n)$。
+然后对所有深度为 $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 题]]

CVBB ACM Team

用户工具

站点工具

页面工具