BZOJ 4337

简单记录一种树哈希的方法:以$x$为根的子树的哈希值为$\sum_{y \in son(x)}f_y*base_i$,$f_y$表示以$y$为根的树的哈希值,其中$i$表示$f_y$在若干个儿子中的排名,$base$是$rand$出的对一个质数取模之后的很大的数。

对于本题这样的情况,可以每一个结点都拿出来作为根计算一下,然后再把所有的结果排个序,如果两棵树同构那么排序之后得到的序列一定是一样的。

时间复杂度$O(n^3)$。

Code:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll; const int N = ;
const ll P = 1e9 + ; int n[N], m, tot, head[N];
ll base[N], h[N][N], f[N];
vector <ll> g[N]; struct Edge {
int to, nxt;
} e[N << ]; inline void add(int from, int to) {
e[++tot].to = to;
e[tot].nxt = head[from];
head[from] = tot;
} inline void read(int &X) {
X = ; char ch = ; int op = ;
for(; ch > '' || ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} void dfs(int x, int fat) {
g[x].clear();
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if(y == fat) continue;
dfs(y, x);
g[x].push_back(f[y]);
} if(g[x].empty()) {
f[x] = 1LL;
return;
} f[x] = 0LL;
sort(g[x].begin(), g[x].end());
int vecSiz = g[x].size();
for(int i = ; i < vecSiz; i++)
(f[x] += g[x][i] * base[i + ] % P) %= P;
} inline bool chk(int x, int y) {
for(int i = ; i <= n[x]; i++)
if(h[x][i] != h[y][i]) return ;
return ;
} int main() {
srand();
for(int i = ; i <= ; i++)
base[i] = rand() * rand() % P * rand() % P * rand() % P * rand() % P; read(m);
for(int i = ; i <= m; i++) {
tot = ;
memset(head, , sizeof(head)); read(n[i]);
for(int fa, j = ; j <= n[i]; j++) {
read(fa);
if(fa) add(j, fa), add(fa, j);
} for(int j = ; j <= n[i]; j++) {
dfs(j, );
h[i][j] = f[j];
}
sort(h[i] + , h[i] + n[i] + );
} for(int i = ; i <= m; i++) {
for(int j = ; j <= i; j++) {
if(n[i] != n[j]) continue;
if(chk(i, j)) {
printf("%d\n", j);
break;
}
}
} return ;
}

最新文章

  1. 使用sublime编写c/c++ 总结
  2. 2-05使用SQL语句创建数据库2
  3. 安装Windows7出现:”安装程序无法创建新的系统分区 也无法定位系统分区“ 终极解决方案
  4. DIV当textarea使用,在聚焦的时候将光标移动到内容的末尾
  5. using namespace std
  6. Ext.NET加入自定义验证JS函数
  7. Begin the new life as a coder
  8. Css3:transform变形
  9. ActiveMQ笔记:源码分析
  10. Chapter 3 Protecting the Data(1):理解权限
  11. servlet与jsp篇(一)$.ajax交互
  12. Jsp的基本知识
  13. PHP字符串处理 单引号 双引号 heredoc nowdoc 定界符
  14. Linux的DNS配置1-DNS入门
  15. FCC JS基础算法题(4):Title Case a Sentence(句中单词首字母大写)
  16. ie-table不显示边框解决办法
  17. SPSS-因子分析
  18. HDU 2057 十六进制加减法
  19. 对Java中的异常的理解
  20. 网站建设之高速WEB的实现

热门文章

  1. RabbitMQ学习系列一安装RabbitMQ服务
  2. 一般在cmd中报不是合法的命令啥的,都是环境变量没有配置好
  3. git自用笔记
  4. hadoop之 Zookeeper 分布式应用程序协调服务
  5. base64图片上传,并根据不同项目进行智能修改图片
  6. java输出数组中出现的次数最多的那个及次数
  7. java代码水仙花
  8. php根据年月获取当月天数。
  9. PHP面向对象深入研究之【继承】,减少代码重复
  10. python开发线程:死锁和递归锁&amp;信号量&amp;定时器&amp;线程queue&amp;事件evevt