树同构-树哈希

题目描述

题解

对于无根树，由于数据范围较小，可以直接以每个点为根dfs一次，维护其树哈希的值，然后用并查集维护
（若数据范围大一些，可以以树的重心跑dfs）

代码实现

#include<bits/stdc++.h>//树哈希 
#define M 100009
#define LL unsigned long long 
using namespace std;
int v[100],vis[100],cnt,n,m;
int tot,first[M],nxt[M],to[M],fat[M];
map<LL,int>ma;
LL f[M],size[M],p[100];
int getfa(int x){if(fat[x]==x) return x;return fat[x]=getfa(fat[x]);
}
void add(int x,int y){nxt[++tot]=first[x];first[x]=tot;to[tot]=y;
}
LL dfs(int u,int fa){size[u]=1,f[u]=1; for(int i=first[u];i;i=nxt[i]){int v=to[i];if(v==fa) continue;f[u]+=dfs(v,u)*p[size[v]];//较好的树哈希方式，不容易被卡 size[u]+=size[v];}return f[u];
}
int main(){int x;scanf("%d",&n);for(int i=1;i<=n;i++) fat[i]=i;for(int i=2;i<=52;i++){if(!v[i]){p[++cnt]=i;v[i]=i;vis[i]=1;} for(int j=1;j<=cnt;j++){if(v[i]<p[j]||i*p[j]>5) break;v[i*p[j]]=p[j];}}for(int i=1;i<=n;i++){scanf("%d",&m),tot=0;memset(first,0,sizeof(first));for(int j=1;j<=m;j++){scanf("%d",&x);if(x)add(j,x),add(x,j);}for(int j=1;j<=m;j++){LL val=dfs(j,0);int w=ma[val];int fx=getfa(i),fy=getfa(w);if(!w) ma[val]=i;else if(fx>fy) fat[fx]=fat[fy],ma[val]=fy;else fat[fy]=fx,ma[val]=fx;}}for(int i=1;i<=n;i++) printf("%d\n",getfa(i));return 0; 
}