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