[关闭]
@ysner 2018-06-10T10:20:55.000000Z 字数 2032 阅读 2110

[JSOI2016]独特的树叶

哈希


题面

有一颗大小为的树,现加上一个节点并打乱编号,形成树,询问加上的节点最后编号是多少?

解析

判断树的同构显然需要树哈希。
可以先将树中以每个节点为根的哈希值算出来存进一只中,
然后在树中随便找一个不是叶节点的节点为根,枚举去掉一个叶节点,看根的值是否能在中找到。
什么?只会求树的哈希值?
我们需要思考一种函数,在根变动时,只影响新根和原根两节点的值,这样就可以每枚举到一个点,就算出其为根时的哈希值。因为要先一遍才能换根,所以复杂度为
并且函数需要很容易去掉某个点的影响。(异或)


一般树哈希还要考虑,当然如果你要换根,考虑的影响就没什么用啦。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<tr1/unordered_set>
  8. #define ll unsigned long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  12. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  13. using namespace std;
  14. const int N=5e5+10,p=1e9+7;
  15. std::tr1::unordered_set<ll>Q;
  16. int h[N],cnt,in[N],sz[N],n;
  17. ll Hash[N],ans=1e18;
  18. struct Edge{int to,nxt;}e[N<<1];
  19. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  20. il void dfs(re int u,re int fa)
  21. {
  22. sz[u]=1;re ll sum=0;
  23. for(re int i=h[u];i+1;i=e[i].nxt)
  24. {
  25. re int v=e[i].to;
  26. if(v==fa) continue;
  27. dfs(v,u);
  28. sz[u]+=sz[v];
  29. Hash[u]=Hash[u]^(Hash[v]+17);
  30. }
  31. Hash[u]+=sz[u]*p+1;
  32. }
  33. il void dfs1(re int u,re int fa)
  34. {
  35. Q.insert(Hash[u]);
  36. for(re int i=h[u];i+1;i=e[i].nxt)
  37. {
  38. re int v=e[i].to;
  39. if(v==fa) continue;
  40. re ll tmp=(Hash[u]-sz[u]*p-1)^(Hash[v]+17);
  41. tmp+=(n-sz[v])*p+1;
  42. Hash[v]-=sz[v]*p+1;
  43. Hash[v]^=(tmp+17);
  44. Hash[v]+=n*p+1;
  45. sz[v]=n;
  46. dfs1(v,u);
  47. }
  48. }
  49. il void dfs2(re int u,re int fa)
  50. {
  51. for(re int i=h[u];i+1;i=e[i].nxt)
  52. {
  53. re int v=e[i].to;
  54. if(v==fa) continue;
  55. re ll tmp=(Hash[u]-sz[u]*p-1)^(Hash[v]+17);
  56. if(in[v]>1)
  57. {
  58. tmp+=(sz[u]-sz[v])*p+1;
  59. Hash[v]-=sz[v]*p+1;
  60. Hash[v]^=(tmp+17);
  61. Hash[v]+=sz[u]*p+1;
  62. sz[v]=sz[u];
  63. dfs2(v,u);
  64. }
  65. else
  66. {
  67. tmp+=(sz[u]-sz[v])*p+1;
  68. if(Q.count(tmp)) ans=min(ans,1ull*v);
  69. }
  70. }
  71. }
  72. int main()
  73. {
  74. memset(h,-1,sizeof(h));
  75. n=gi();
  76. fp(i,1,n-1)
  77. {
  78. re int u=gi(),v=gi();
  79. add(u,v);add(v,u);
  80. }
  81. dfs(1,0);//计算树A哈希值
  82. dfs1(1,0);//换根算树A哈希值
  83. memset(h,-1,sizeof(h));memset(Hash,0,sizeof(Hash));
  84. fp(i,1,n)
  85. {
  86. re int u=gi(),v=gi();
  87. ++in[u];++in[v];
  88. add(u,v);add(v,u);
  89. }
  90. re int i;
  91. for(i=1;i<=n;i++) if(in[i]>1) break;//随便找一个不是叶节点的节点为根
  92. dfs(i,0);//算树B哈希值
  93. dfs2(i,0);//对叶子节点,试去掉它会怎么样;对非叶子节点,进行换根DP
  94. printf("%lld\n",ans);
  95. return 0;
  96. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注