[关闭]
@ysner 2018-06-08T22:31:13.000000Z 字数 3318 阅读 1924

[BJOI2015]树的同构

树哈希


题面

给出各种形态的树,问哪些树互为重构树?

解析

一开始没注意到不论树有没有根,都要以树的重心为根,根的不同可以改变树的形态,如一棵树变成一条链之类。
树的重心的要求是使子树 最大规模 最小
显然使用树哈希。


看起来这式子很容易乘爆,我们可以模一个(自然溢出也是同一原理),以减少对 大小在模数范围以内 的二进制位的影响。
最后再注意一下找完后要重新统计子树大小
但在上死都过不了,很想蒯数据

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=105,mod1=498353,mod2=412817,mod=1<<30;
  14. int n,h[N],cnt,m,B1=3,B2=7,B3=11,sz[N],vis1[500000],vis2[500000],dp[N],root;
  15. ll Hash[N];
  16. struct Edge{int to,next;}e[N<<1];
  17. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  18. il void dfs(re int u,re int fa,re int deep)
  19. {
  20. //printf("%d %d %d\n",u,fa,deep);
  21. re ll sum=0;sz[u]=1;
  22. for(re int i=h[u];i+1;i=e[i].next)
  23. {
  24. re int v=e[i].to;
  25. if(v==fa) continue;
  26. dfs(v,u,deep+1);//printf("%d\n",Hash[v]);
  27. sum^=Hash[v];
  28. sz[u]+=sz[v];
  29. }
  30. Hash[u]^=((sum+B1)*(sz[u]+B2)*(deep+B3));
  31. Hash[u]%=mod;
  32. //printf("%lld %d\n",Hash[u],u);
  33. }
  34. il void getroot(re int u,re int fa)
  35. {
  36. sz[u]=1;
  37. for(re int i=h[u];i+1;i=e[i].next)
  38. {
  39. re int v=e[i].to;
  40. if(v==fa) continue;
  41. getroot(v,u);
  42. sz[u]+=sz[v];
  43. dp[u]=max(dp[u],sz[v]);
  44. }
  45. dp[u]=max(dp[u],n-dp[u]);
  46. if(dp[u]<dp[root]) root=u;
  47. else if(dp[u]==dp[root]&&u<root) root=u;
  48. }
  49. int main()
  50. {
  51. m=gi();
  52. fp(o,1,m)
  53. {
  54. memset(h,-1,sizeof(h));cnt=0;memset(Hash,0,sizeof(Hash));memset(dp,0,sizeof(dp));dp[0]=1e9;memset(sz,0,sizeof(sz));
  55. n=gi();root=0;
  56. fp(i,1,n)
  57. {
  58. re int v=gi();
  59. if(v) add(i,v),add(v,i);
  60. }
  61. getroot(1,0);//printf("%d %d\n",o,root);
  62. dfs(root,0,1);//printf("%d %lld\n",o,Hash[1]);
  63. if(vis1[Hash[root]%mod1]&&vis2[Hash[root]%mod2]) printf("%d\n",vis1[Hash[root]%mod1]);
  64. else printf("%d\n",vis1[Hash[root]%mod1]=vis2[Hash[root]%mod2]=o);
  65. }
  66. return 0;
  67. }

在对进行排序后,
哈希方程变为这样(为当前节点,为子节点,为质数表)


当然当前节点也算单独一颗的子树,要不然叶节点怎么办。。。
因该式不考虑诸如深度、以该节点为根的子树等因素,我们就要对每个点为根的情况都进行值计算,最后排序以后比较是否完全相同即可。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=105;
  14. int n,h[N],cnt,m,p[55];
  15. ll Hash[N][N],dp[N];
  16. struct Edge{int to,next;}e[N<<1];
  17. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  18. il ll gi()
  19. {
  20. re ll x=0,t=1;
  21. re char ch=getchar();
  22. while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  23. if(ch=='-') t=-1,ch=getchar();
  24. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25. return x*t;
  26. }
  27. il void wri(re int x)
  28. {
  29. if(x<0) putchar('-'),x=-x;
  30. if(x>9) wri(x/10);
  31. putchar(x%10+'0');
  32. }
  33. il void dfs(re int u,re int fa)
  34. {
  35. re ll top=0,s[55];s[++top]=1;
  36. for(re int i=h[u];i+1;i=e[i].next)
  37. {
  38. re int v=e[i].to;
  39. if(v==fa) continue;
  40. dfs(v,u);
  41. s[++top]=dp[v];
  42. }
  43. dp[u]=0;sort(s+1,s+1+top);
  44. fp(i,1,top) dp[u]+=s[i]*p[i];
  45. }
  46. il void Pre()
  47. {
  48. re int tot=0;
  49. fp(i,41,300)
  50. {
  51. re int flag=1;
  52. fp(j,2,sqrt(i)) if(i%j==0) {flag=0;break;}
  53. if(flag) p[++tot]=i;
  54. if(tot>50) break;
  55. }
  56. }
  57. int main()
  58. {
  59. Pre();
  60. m=gi();
  61. fp(o,1,m)
  62. {
  63. memset(h,-1,sizeof(h));cnt=0;memset(dp,0,sizeof(dp));
  64. n=gi();
  65. fp(i,1,n)
  66. {
  67. re int v=gi();
  68. if(v) add(i,v),add(v,i);
  69. }
  70. fp(i,1,n) dfs(i,0),Hash[o][i]=dp[i];
  71. sort(Hash[o]+1,Hash[o]+1+n);
  72. //fp(i,1,n) printf("%lld ",Hash[o][i]);puts("");
  73. fp(i,1,o)
  74. {
  75. re int flag=1;
  76. fp(j,1,n) if(Hash[o][j]!=Hash[i][j])
  77. {
  78. //printf("%d %d %lld\n",i,j,Hash[i][j]);
  79. flag=0;break;
  80. }
  81. if(flag) {printf("%d\n",i);break;}
  82. }
  83. }
  84. return 0;
  85. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注