1 条题解
-
0
摘自《浅谈哈希》。
树哈希
P5043 【模板】树同构 / [BJOI2015] 树的同构
思考如何把一棵无根树映射到一个整数,感觉很难做。不妨把重心作为根,求出有根树哈希值(双重心把两个哈希值打包即可)。我们有这样一个正统的有根树多项式哈希函数:
$$H(u) = \left(1+\sum_{i} H(\text{son}(u,i)) \times b^{i}\right) \bmod M $$其中 表示 的儿子按哈希值排序后的第 个儿子编号。最劣复杂度 。原理其实就是不让节点编号影响哈希值。
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<map> #include<random> #define int long long #define ull unsigned long long using namespace std; const int base=3; int n,m,maxx,cnt,id[57],fa[57],sz[57]; ull h[57]; vector<int> tr[57]; vector<ull> hs; map<ull,int> mp; void DFS1(int u,int f){ sz[u]=1; int x=-1; for(int v : tr[u]){ if(v==f) continue; DFS1(v,u); sz[u]+=sz[v]; x=max(x,sz[v]); } x=max(x,n-sz[u]); if(x>maxx) maxx=x,id[cnt=1]=u; else if(x==maxx) id[++cnt]=u; } void DFShs(int u,int f){ h[u]++; for(int v : tr[u]) if(v!=f) DFShs(v,u); sort(tr[u].begin(),tr[u].end(),[](int x,int y){ return h[x]<h[y]; }); ull p=1; for(int v : tr[u]){ if(v==f) continue; h[u]+=h[v]*p; p=p*base; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>m; for(int t=1;t<=m;t++){ cin>>n; for(int i=0;i<=n;i++) tr[i].clear(); int root; for(int i=1;i<=n;i++){ cin>>fa[i]; if(fa[i]){ tr[fa[i]].push_back(i); tr[i].push_back(fa[i]); } else root=i; } maxx=-1,cnt=0; DFS1(root,0); int res=0; for(int i=1;i<=cnt;i++){ for(int j=0;j<=n;j++) h[j]=0; DFShs(id[i],0); res+=h[id[i]]; } if(!mp[res]) mp[res]=t; cout<<mp[res]<<'\n'; } return 0; }另外附一个好写且卡不掉的严格线性树哈希,OI-wiki 也改成这个了,可以学一学。
推荐例题 P4323。
信息
- ID
- 159
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 15
- 已通过
- 7
- 上传者