首页 > 其他分享 >【模板】树哈希

【模板】树哈希

时间:2024-10-09 21:01:01浏览次数:10  
标签:hash int shift hsh long 哈希 word 模板

https://peehs-moorhsum.blog.uoj.ac/blog/7891

题目描述

对一棵树求 hash 值,以判断两棵树是否同构。有有根树和无根树两个版本。

solution

找一个随机函数 \(f\)(可以选 xor-shift),然后每个点的子树的哈希值如下计算:

\[h_u=1+\sum_{v}f(h_v) \]

这是有根树的情况,对于无根树,1. 可以换根 dp 求出以任意点为根的 hash 值,然后取最小的;2. 找重心,求出重心为根的 hash 值,有两个重心取 hash 值较小的。

code

P5043 【模板】树同构([BJOI2015]树的同构)

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
using word = unsigned long long;
mt19937_64 rng{random_device{}()};
const word mask = rng();
word shift(word x) {
  x ^= mask;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  return x ^ mask;
}
int n, m;
basic_string<int> g[1000010];
word f[1000010], hsh[1000010];
word dfs(int u, int fa) {
  word &ans = f[u] = 1;
  for (int v : g[u]) if (v != fa) ans += shift(dfs(v, u));
  return ans;
}
void dfs2(int u, int fa) {
  for (int v : g[u]) if (v != fa) f[v] += shift(f[u] - shift(f[v])), dfs2(v, u);
}
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  cin >> m;
  map<word, int> mp;
  for (int t = 1; t <= m; t++) {
    cin >> n;
    for (int i = 1; i <= n; i++) g[i].clear();
    for (int i = 1, x; i <= n; i++) {
      cin >> x;
      if (x) g[i] += x, g[x] += i;
    }
    dfs(1, 0);
    dfs2(1, 0);
    hsh[t] = *min_element(f + 1, f + n + 1);
    if (!mp.count(hsh[t])) mp[hsh[t]] = t;
  }
  for (int i = 1; i <= m; i++) cout << mp[hsh[i]] << endl;
  return 0;
}

标签:hash,int,shift,hsh,long,哈希,word,模板
From: https://www.cnblogs.com/caijianhong/p/18455143/template-tree-hash

相关文章

  • 1:1仿PG电子PP电子 后台可控 多个模板选择源码全开源 像项目展示
    前端首页页面前端登录界面前端支持多套UI支持多种语言效果后端游戏控制界面后端游戏添加界面后端模板切换页面仅供参考!......
  • C++模板与容器
    目录一、 模板1.函数模板2.类模板二、容器1.标准模板库STL2.概念3顺序容器3.1array数组2.3.2vector向量3.3list列表 3.4deque队列4关联容器5迭代器遍历一、 模板        模板可以让类或者函数支持一种通用类型,这种通用数据类型在实......
  • 洛谷 P7469 [NOI Online 2021 提高组] 积木小赛(字符串哈希)
    题目传送门解题思路读题后,我们可以发现,字母串  只能从两边删除,于是我们可以枚举一个区间 ,然后在字母串  中匹配(可以用指针来进行匹配),同时可以做字符串哈希去重。注意如果怕被卡,可以用双模哈希;记得开longlong代码#include<bits/stdc++.h>usingnamespacestd;......
  • 洛谷题单指南-字符串-P3375 【模板】KMP
    原题链接:https://www.luogu.com.cn/problem/P3375题意解读:给定两个字符串:原串s,模式串p,求p在s中出现的所有位置,并输出p的长度为1~p.size()的子串的最长相同真前、后缀的长度。解题思路:KMP模版题,分两问,第一问通过KMP核心算法实现,第二问输出模式串的Next数组内容,接下来一一解读。......
  • python3常用库之哈希hashlib和hmac使用
    hashlibimporthashlib#MD5是最常见的哈希算法,速度很快,生成结果是固定的128bit/16字节,通常用一个32位的16进制字符串表示。md5=hashlib.md5()md5.update("hello".encode())print(md5.hexdigest())#5d41402abc4b2a76b9719d911017c592#数据量很大时分块多次调用up......
  • Axure大屏可视化模板在多领域实践应用案例分析
    Axure大屏可视化模板,凭借其强大的功能性和灵活性,在众多领域中发挥着举足轻重的作用。本文将详细探讨Axure大屏可视化模板在农业、园区管理、智慧城市、企业数据可视化和医疗领域的应用案例,展示其如何助力各行业实现智能化管理和决策优化。一、农业领域:智慧农业的得力助手智慧......
  • 网站模板修改步骤是什么
    网站模板的修改通常涉及以下几个步骤:备份现有网站:在进行任何修改之前,首先应该备份当前网站的所有文件和数据库,以防修改过程中出现问题可以快速恢复。确定修改需求:明确你希望对模板进行哪些方面的修改,比如设计风格、功能增强或是布局调整等。选择合适的编辑工具:根据模板的......
  • springboot-网站开发-thymeleaf引擎报错找不到指定的页面模板文件
    springboot-网站开发-thymeleaf引擎报错找不到指定的页面模板文件!这种错误的情况,发生,一般都是因为,我们自己的html模板文件,存档位置并不是在默认的templates下面。而是我们自己新建的一个子目录里面。然后,我们在java代码里面,控制器方法体内,return,返回模板的时候,我们多写了一个......
  • 怎么修改模板上的内容?更改模板
    要修改模板上的内容或更改模板,通常需要遵循以下步骤:定位模板文件:首先找到你想要修改的模板文件的位置。这通常取决于你使用的开发环境和框架。例如,在Web开发中,模板文件可能位于项目的views或templates目录下。编辑模板内容:使用文本编辑器打开模板文件。根据需求修改模板......
  • 【模板】"动态DP"&动态树分治
    目录题目描述朴素算法矩阵刻画实现code以洛谷模板题为例介绍动态dp的一般方法。P4719【模板】"动态DP"&动态树分治-洛谷|计算机科学教育新生态(luogu.com.cn)P4751【模板】"动态DP"&动态树分治(加强版)-洛谷|计算机科学教育新生态(luogu.com.cn)题目描述给定一......