【BZOJ - 4337】BJOI2015 树的同构（树哈希）

题干：

树是一种很常见的数据结构。

我们把N个点，N-1条边的连通无向图称为树。

若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。

对于两个树T1和T2，如果能够把树T1的所有点重新标号，使得树T1和树T2完全相

同，那么这两个树是同构的。也就是说，它们具有相同的形态。

现在，给你M个有根树，请你把它们按同构关系分成若干个等价类。

Input

第一行，一个整数M。

接下来M行，每行包含若干个整数，表示一个树。第一个整数N表示点数。接下来N

个整数，依次表示编号为1到N的每个点的父亲结点的编号。根节点父亲结点编号为0。

Output

输出M行，每行一个整数，表示与每个树同构的树的最小编号。

Sample Input

4 4 0 1 1 2 4 2 0 2 3 4 0 1 1 1 4 0 1 2 3

Sample Output

1 1 3 1

Hint

【样例解释】 

编号为1, 2, 4 的树是同构的。编号为3 的树只与它自身同构。 

100% 的数据中，1 ≤ N, M ≤ 50。 

题目大意：

  中文题意不解释了。

解题报告：

  直接转化成无根树然后扔到set中，然后对于每一个求ans的时候直接暴力判断就好。所以对于每一棵树都要随便找一个点的Hash值当做代表值（这里用的是H[1]），再去set中判断。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 55 + 5; const ll MOD = 2000004199; //用这个模数都没有问题！ const ll seed = 13331;//可换！ ll INV; struct Edge {int v,ne; } e[MAX<<1]; int head[MAX],tot; int n,m; void adde(int u,int v) {e[++tot].v = v;e[tot].ne = head[u]; head[u] = tot; } inline ll qpow(ll a,ll b) {ll res = 1;while(b) {if(b&1) res = res * a % MOD;a = a *a % MOD;b >>= 1; }return res; } inline ll add(ll x,ll y) {return (x+y)%MOD;} inline ll mul(ll x,ll y) {return (x*y)%MOD;} inline ll sub(ll x,ll y) {return (x-y+MOD)%MOD;} ll H[MAX]; int size[MAX],du[MAX]; void dfs(int cur,int fa) {H[cur] = 1;size[cur] = 1;for(int i = head[cur]; ~i; i = e[i].ne) {int v = e[i].v;if(v == fa) continue;dfs(v,cur);size[cur] = add(size[cur],size[v]);H[cur] = mul(H[cur],H[v]);}H[cur] = add(H[cur],size[cur]);H[cur] = mul(H[cur],seed); } set<ll> ss[MAX]; void dfs1(int num,int cur,int fa) {ss[num].insert(H[cur]);//必须要先插入，因为根的情况。 ll Hall = mul(H[cur],INV),Hres;Hall = sub(Hall,n);for(int i = head[cur]; ~i; i = e[i].ne) {int v = e[i].v;if(v == fa) continue;Hres=mul(Hall,qpow(H[v],MOD-2));Hres=add(Hres,n-size[v]); Hres=mul(Hres,seed);//至此Hres代表除v的树的Hash值H[v]=mul(H[v],INV); H[v]=sub(H[v],size[v]);H[v]=mul(H[v],Hres);H[v]=add(H[v],n);H[v]=mul(H[v],seed);dfs1(num,v,cur);} } void init() {tot=0;memset(head,-1,sizeof head); } ll ans[MAX]; int main() {INV = qpow(seed,MOD-2);cin>>m;for(int u,v,i = 1; i<=m; i++) {cin>>n;init();for(int j = 1; j<=n; j++) {cin>>u;if(u == 0) continue;adde(u,j);adde(j,u);}dfs(1,0);dfs1(i,1,0);ans[i] = H[1];}for(int i = 1; i<=m; i++) {for(int j = 1; j<=i; j++) {if(ss[j].count(ans[i])) {ans[i] = j;break;}}for(int i = 1; i<=m; i++) printf("%lld\n",ans[i]);return 0 ; }

 

总结

以上是生活随笔为你收集整理的【BZOJ - 4337】BJOI2015 树的同构（树哈希）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。