学习笔记——树上哈希

普通子树哈希

树上的很多东西都是转化成链上问题的,比如树上哈希
树上哈希,主要是用于树的同构这个东西上的
什么是树的同构?

如图,不考虑节点编号,三棵树是同构的

将树转化成链,一般有两种方式:环游欧拉序与欧拉序
为了尽可能减少哈希冲突,进制位越小越好
又因为不考虑节点编号,很明显,若是采用欧拉序的话,得要记录该节点孩子数
环游欧拉序只用进入打上1,出来打上2即可搞定
小tips:欧拉序相较于环游欧拉序可能更快,请量力而行

于是,就可以采用普通的哈希方式啦!

指定范围子树哈希

如果说是将子树横着割一刀呢?
如图,是一棵树

放心,就60个节点
我们考虑D节点的子树中,距离D不超过3的所有点
如图

接着是环游欧拉序(考虑在某些原因的份上,我只保留D的子树)

为什么我只写到10?因为作者实在太懒因为到10就够了
对于范围树上哈希,我们有两种方式——拼接与删除
因为哈希一般在取模的意义下,所以,删除是非常难以做到的~~(作者亲测过)~~
那只剩下拼接了,这个就和链上拼接一模一样了(也很像是前缀和)

模板题


题目主要考的是范围树上哈希

如果说看懂了前面的,这题就不难了。首先可以二分。因为若是 k k k是答案,那么一定存在两个节点的 k k k层子树是同构的。在其中任选两个对应的点,所组成的子树的子树一定是同构的
这么说显得很烦,翻译成人化就是:对于每个符合题目要求的 k k k层的两个子树(就是这两个字叔同构),他们的所有子树中一定有同构的,并且层数有 0 0 0、有 1 1 1、有 ⋯ \cdots 、有 k − 1 k-1 k1

于是,题目就这样转化成了求是否存在同构的 k k k层子树
我们可以对于每个节点,求出它的 k k k层祖先,代表这个节点绝对存在 k k k层子树;
再找出 k + 1 k+1 k+1曾祖先,代表这个节点的子树将要在他的祖先的子树中被删去(不被添加)
最后用一个map(建议使用gp_hash_table)统计答案
题目就这么结束了

代码

#pragma GCC optimize(1, "inline", "Ofast")
#pragma GCC optimize(2, "inline", "Ofast")
#pragma GCC optimize(3, "inline", "Ofast")
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
namespace IO {
class input {
private:bool isdigit(char c) { return ('0' <= c && c <= '9'); }public:input operator>>(int &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(short &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(bool &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(long &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(long long &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(__int128 &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(unsigned int &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(unsigned short &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(unsigned long &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(unsigned long long &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(unsigned __int128 &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(double &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();if (!y)x = -x;if (!isdigit(c))if (c != '.')return *this;double z = 1;while (isdigit(c)) z /= 10., x = x + z * (c ^ 48), getchar();return *this;}input operator>>(long double &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();if (!y)x = -x;if (!isdigit(c))if (c != '.')return *this;double z = 1;while (isdigit(c)) z /= 10., x = x + z * (c ^ 48), c = getchar();return *this;}input operator>>(float &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();if (!y)x = -x;if (!isdigit(c))if (c != '.')return *this;double z = 1;while (isdigit(c)) z /= 10., x = x + z * (c ^ 48), c = getchar();return *this;}input operator>>(std::string &x) {char c = getchar();x.clear();while (!(c != ' ' && c != '\n' && c != '	' && c != EOF && c)) c = getchar();while (c != ' ' && c != '\n' && c != '	' && c != EOF && c) {x.push_back(c);c = getchar();}return *this;}input operator>>(char *x) {char c = getchar();int cnt = 0;while (!(c != ' ' && c != '\n' && c != '	' && c != EOF && c)) c = getchar();while (c != ' ' && c != '\n' && c != '	' && c != EOF && c) {x[cnt++] = c;c = getchar();}return *this;}input operator>>(char x) {x = getchar();return *this;}
} pin;
};  // namespace IO
inline void wt(char ch) { putchar(ch); }
template <class T>
inline void wt(T x) {static char ch[40];int p = 0;if (x < 0)putchar('-'), x = -x;doch[++p] = (x % 10) ^ 48, x /= 10;while (x);while (p) putchar(ch[p--]);
}
template <class T, class... U>
inline void wt(T x, U... t) {wt(x), wt(t...);
}
#define int unsigned long long
const int N = 1e5 + 7;
int n;
const int M = 2e5 + 7;
struct edge {int v, w, nxt;
} e[M];
int head[N], ct;
const int T = 19, K = 3;
int ll[N], x[M], nx[N];//x一定要开两倍!!!
int l[N], r[N];
int tp;
int getpw(int d) { return ll[d]; }
void addE(int u, int v, int w = 0) {e[++ct] = { v, w, head[u] };head[u] = ct;
}
void saddE(int u, int v, int w = 0) { addE(u, v, w), addE(v, u, w); }
int fa[N][T + 1];
__gnu_pbds::gp_hash_table<int, bool> cun;
void getx(int u = 1, int faa = 0) {l[u] = ++tp;x[tp] = (x[tp - 1] * K + 1);fa[u][0] = faa;for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].v;getx(v, u);}r[u] = ++tp;x[tp] = (x[tp - 1] * K + 2);
}
int ytl[N];
typedef pair<int, int> pii;
vector<pii> vt[N];
bool chk(int mid) {memset(nx, 0, sizeof nx);cun.clear();memset(ytl, 0, sizeof ytl);for (int i = 1; i <= n; i++) vt[i].clear();for (int i = 1; i <= n; i++) {int tl = i;for (int j = T, k = mid; ~j; j--)if ((1ull << j) <= k)k -= (1ull << j), tl = fa[tl][j];if (tl == 0)continue;ytl[tl] = 1;tl = fa[tl][0];if (tl == 0)continue;// out<<i<<" "<<tl<<endl;vt[tl].push_back(pii(l[i], i));}for (int i = 1; i <= n; i++) sort(vt[i].begin(), vt[i].end());bool flg = 0;for (int i = 1; i <= n; i++) {if (!ytl[i])continue;int lr = l[i];for (auto j : vt[i]) {int k = j.second;//	cout<<k<<endl;(nx[i] *= getpw(l[k] - lr));(nx[i] += x[l[k] - 1] - (x[lr - 1] * getpw(l[k] - lr)));//	cout<<x[l[k]-1]<<" "<<x[lr-1]<<" "<<nx[i]<<endl;lr = r[k] + 1;}(nx[i] *= getpw(r[i] - lr + 1));(nx[i] += x[r[i]] - (x[lr - 1] * getpw(r[i] - lr + 1)));if (cun[nx[i]])return 1;// cout<<nx[i]<<endl;cun[nx[i]] = 1;//	cout<<nx[i]<<endl;//	puts("");}return flg;
}
main() {freopen("tree.in", "r", stdin);freopen("tree.out", "w", stdout);ll[0] = 1;for (int i = 1; i < N; i++) ll[i] = (ll[i - 1] * K);IO::pin >> n;for (int i = 1, x, y; i <= n; i++) {IO::pin >> x;while (x--) IO::pin >> y, addE(i, y);}getx();for (int j = 1; j <= T; j++)for (int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1];int l = 0, r = n - 1;while (l < r) {int mid = l + r + 1 >> 1;// cout<<l<<" "<<r<<" "<<mid<<endl;if (chk(mid))l = mid;elser = mid - 1;}printf("%llu\n", l);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/127247.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

JS防抖和节流在前端开发中的应用场景

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 防抖&#xff08;Debouncing&#xff09;⭐ 节流&#xff08;Throttling&#xff09;⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端…

KT142C-sop16语音芯片ic内置320Kbyte_USB更新内置空间详细说明

KT142C内置的是320K的空间&#xff0c;但是实际的大小&#xff0c;在电脑里面显示&#xff0c;应该是315Kbyte。 打开我的电脑&#xff0c;芯片连接PC之后&#xff0c;自动多出来了一个U盘&#xff0c;如下图所示&#xff1a; 这里的空间只有315KB &#xff0c;因为文件系统占…

猫头虎的技术笔记:Spring Boot启动报错解决方案

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

Java项目基于SpringBoot藏区特产销售系统,可作为毕业设计

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W,Csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 今天为大家带来的是基于 Java SpringBootVue 的藏区特产销售系统 文章目录 1. 简介2.主要技术3 功能分析4 系…

【2023高教社杯】B题 多波束测线问题 问题分析、数学模型及参考文献

【2023高教社杯】B题 多波束测线问题 问题分析、数学模型及参考文献 1 题目 1.1 问题背景 多波束测深系统是利用声波在水中的传播特性来测量水体深度的技术&#xff0c;是在单波束测深的基础上发展起来的&#xff0c;该系统在与航迹垂直的平面内一次能发射出数十个乃至上百个…

Redis集群3.2.11离线安装详细版本(使用Ruby)

1.安装软件准备 1.Redis版本下载 Index of /releases/http://download.redis.io/releases/ 1.2gcc环境准备 GCC(GNU Compiler Collection,GNU编译器套件)是一套用于编译程序代码的开源编译器工具集。它的主要用途是将高级编程语言(如C、C++、Fortran等)编写的源代码转换…

SEO百度优化基础知识全解析(了解百度SEO标签作用)

百度SEO优化的作用介绍&#xff1a; 百度SEO优化是指通过对网站的内部结构、外部链接、内容质量、用户体验等方面进行优化&#xff0c;提升网站在百度搜索结果中的排名&#xff0c;从而提高网站的曝光率和流量。通过百度SEO优化&#xff0c;可以让更多的潜在用户找到你的网站&…

软件设计模式(二):工厂、门面、调停者和装饰器模式

前言 在这篇文章中&#xff0c;荔枝将会梳理软件设计模式中的四种&#xff1a;工厂模式、Facade模式、Mediator模式和装饰器Decorator模式。其中比较重要的就是工厂模式和装饰器模式&#xff0c;工厂模式在开发中使用的频数比较高。希望荔枝的这篇文章能讲清楚哈哈哈哈&#xf…

【STM32】文件系统FATFS与Flash的初步使用

文件系统简介 简介可以不看&#xff0c;直接看移植步骤 文件系统是介于应用层和底层间的模糊层。底层提供API&#xff0c;比如说使用SDIO或者SPI等读写一个字节。文件系统把这些API组合包装起来&#xff0c;并且提供一些列函数&#xff0c;我们可以使用这些函数进行更进一步的…

分享一个python基于数据可视化的智慧社区服务平台源码

&#x1f495;&#x1f495;作者&#xff1a;计算机源码社 &#x1f495;&#x1f495;个人简介&#xff1a;本人七年开发经验&#xff0c;擅长Java、Python、PHP、.NET、Node.js、微信小程序、爬虫、大数据等&#xff0c;大家有这一块的问题可以一起交流&#xff01; &#x1…

MySQL数据类型

目录 MySQL数据类型 数据类型分类 数值类型 tinyint类型 bit类型 float类型 decimal类型 字符串类型 char类型 varchar类型 char和varchar比较 时间日期类型 enum和set类型 MySQL数据类型 数据类型的作用&#xff1a; 决定了存储数据时应该开辟的空间大小。决定…

CocosCreator3.8研究笔记(十二)CocosCreator 字体资源理解

Cocos Creator 常用的字体资源有三种&#xff1a;系统字体、动态字体、位图字体。 一、系统字体 系统字体是调用运行平台自带的系统字体来渲染文字&#xff0c;不需要用户在项目中添加任何相关资源。 使用系统字体&#xff0c; Label 组件 Use System Font 属性需要勾选。 Fo…

手写签名到背景上合为1张图

手写签名到背景上合为1张图 package.json中 "signature_pad": "3.0.0-beta.3"<template><div class"home"><canvas id"canvas" width"500" height"300"></canvas><button click"…

【计算机基础知识4】网络通信协议:TCP、UDP、WebSockets

目录 一、TCP&#xff08;传输控制协议&#xff09; 1. TCP的特点 2. TCP的连接建立和终止 3. TCP的可靠性机制 4. TCP的流量控制 二、UDP&#xff08;用户数据报协议&#xff09; 1. UDP的特点 2. UDP的使用场景 三、WebSockets 1. WebSockets协议的特点 2. WebSock…

长安链BaaS服务平台调研

目录 一、菜单功能二、其他说明2.1、服务平台的部署方式2.2、链本身2.3、建链流程2.4、支持连接已部署的链2.5、链治理投票2.6、支持动态节点操作2.7、支持应用 长安链ChainMaker管理平台文档地址&#xff1a;https://docs.chainmaker.org.cn 一、菜单功能 菜单子菜单/功能点…

强大的JTAG边界扫描(1):基本原理介绍

文章目录 1. 什么是边界扫描&#xff1f;2. JTAG硬件接口3. 边界扫描相关的软硬件4. 学习资料5. 总结 我是怎么了解到边界扫描的呢&#xff1f; 这就要从我淘到一块FPGA板卡的事情说起了。 前段时间我在某二手平台上淘了一块FPGA板子&#xff0c;它长这样&#xff1a; 板子的…

【广州华锐互动】元宇宙技术如何赋能传统工业企业?

随着科技的飞速发展&#xff0c;我们正处于工业革命4.0的时代&#xff0c;数字化、网络化和智能化正在深刻地改变着我们的生活和工作方式。在这个变革的大潮中&#xff0c;工业元宇宙平台应运而生&#xff0c;为企业带来了前所未有的机遇和挑战。 广州华锐互动开发的工业元宇宙…

vite搭建vue3项目

参考视频 1.使用npm搭建vite项目,会自动搭建vue3项目 npm create vitelatest yarn create vite2.手动搭建vue3项目 创建一个项目名称的文件夹执行命令&#xff1a;npm init -y 快速的创建一个默认的包信息安装vite: npm i vite -D -D开发环境的依赖 安装vue,现在默认是vue3.…

nodejs下载指定版本

1.搜索nodejs打开官网nodejs官网&#xff08;除了去官网下载之外还可以使用nvm下载&#xff09; 2.点击downloads 3.往下滑点击Previous Releases(以前的版本) 4.找到你想下载的版本点开&#xff08;此处可能没你想要的具体版本&#xff0c;没关系找到大版本号相同的点开就行了…

【PowerQuery】Excel 的自动刷新功能-最低一分钟刷新

在Excel集成了PowerQuery之后,它提供了数据的手动刷新功能之外,也提供了数据的自动刷新功能。需要注意的是,PowerQuery提供的自动刷新功能是针对连接的,也就是说在PowerQuery自动刷新功能不是全局刷新功能,而是针对连接本身提供。接下来我们来看一下如何实现PowerQuery连接…