本文主要是介绍Codeforces 1252 F Regular Forestation —— 树哈希判同构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
This way
题意：
给你一棵树，让你去掉任意一个非叶子结点的点，使得这棵树变成多棵树，如果这些树同构，那么就当是有效的删除，问你在有效的删除中，最多有多少同构树
题解：
显而易见，有效的删除最多只有一种。并且删除的点一定是重心，那么就要判剩下的树是否同构了，新学了一个知识点叫树哈希，其实就是枚举每一个点为根的时候的哈希值。我用了两种方法，第一种是将当前节点的儿子哈希值排序然后一个一个加入当前的哈希值。这个单哈希也能过，第二种是加上儿子节点的哈希值乘一个质数，因为这种就无论先后了。。但是不知道为什么过不了，双哈希也不行：
h=h+pri[siz[ne]]*f_hash(ne,x);
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=4e4+5;
struct node{int to,next;
}e[N*2];
int cnt,head[N];
void add(int x,int y){e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt++;
}
int siz[N],n;
int f_siz(int x,int fa){siz[x]=1;for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(ne==fa)continue;f_siz(ne,x);siz[x]+=siz[ne];}
}
int f_rt(int x,int fa){for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(ne==fa)continue;if(siz[ne]>n/2)return f_rt(ne,x);}return x;
}
int rt;
vector<int>vec;
void f_p(int x,int fa){vec.push_back(x);for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(ne!=fa)f_p(ne,x);}
}
ull f_hash(int x,int fa){vector<ull>v;for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(ne==fa||ne==rt)continue;v.push_back(f_hash(ne,x));}sort(v.begin(),v.end());ull h=28;for(auto i:v)h=h*131ll+i;return h;
}
vector<ull>ans[2];
int main()
{scanf("%d",&n);memset(head,-1,sizeof(head));int x,y;for(int i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);f_siz(1,0);rt=f_rt(1,0);f_siz(rt,0);int pre=-1;for(int i=head[rt];~i;i=e[i].next){int ne=e[i].to;if(pre==-1)pre=siz[ne];elseif(pre!=siz[ne])return 0*printf("-1\n");}int now=0,all=0;for(int i=head[rt];~i;i=e[i].next){all++;int ne=e[i].to;vec.clear();f_p(ne,rt);for(auto j:vec)ans[now].push_back(f_hash(j,0));sort(ans[now].begin(),ans[now].end());if(now==0){now=1;continue;}for(int j=0;j<ans[1].size();j++)if(ans[1][j]!=ans[0][j])return 0*printf("-1\n");ans[1].clear();}printf("%d\n",all);return 0;
}
这篇关于Codeforces 1252 F Regular Forestation —— 树哈希判同构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
