当前位置: 首页 > news >正文

学习笔记——树上哈希

普通子树哈希

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

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

将树转化成链,一般有两种方式:环游欧拉序与欧拉序
为了尽可能减少哈希冲突,进制位越小越好
又因为不考虑节点编号,很明显,若是采用欧拉序的话,得要记录该节点孩子数
环游欧拉序只用进入打上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);
}

相关文章:

学习笔记——树上哈希

普通子树哈希 树上的很多东西都是转化成链上问题的&#xff0c;比如树上哈希 树上哈希&#xff0c;主要是用于树的同构这个东西上的 什么是树的同构&#xff1f; 如图&#xff0c;不考虑节点编号&#xff0c;三棵树是同构的 将树转化成链&#xff0c;一般有两种方式&#xf…...

Opencv快速入门教程,Python计算机视觉基础

快速入门 OpenCV 是 Intel 开源计算机视觉库。它由一系列 C 函数和少量 C 类构成&#xff0c; 实现了图像处理和计算机视觉方面的很多通用算法。 OpenCV 拥有包括 300 多个 C 函数的跨平台的中、高层 API。它不依赖于其它的外部库——尽管也 可以使用某些外部库。 OpenCV 对非…...

laravel 报错误信息 Carbon\Exceptions\InvalidFormatException

Carbon\Exceptions\InvalidFormatException Unexpected data found. at vendor\nesbot\carbon\src\Carbon\Traits\Creator.php:687 683▕ return $instance; 684▕ } 685▕ 686▕ if (static::isStrictModeEnabled()) { ➜ 687…...

UI自动化之混合框架

什么是混合框架&#xff0c;混合框架就是将数据驱动与关键字驱动结合在一起&#xff0c;主要用来回归业务主流程&#xff0c;将核心流程串联起来。 上一篇我们写到了关键字驱动框架&#xff0c;关键字驱动框架是针对一个业务场景的单条测试用例的。 我们以163邮箱的登录到创建…...

SQL创建用户-非DM8.2环境(达梦数据库)

DM8:达梦数据库SQL创建用户-非DM8.2环境 环境介绍 环境介绍 在没有图形化界面&#xff0c;或者想快速创建用户&#xff0c;可以使用一下SQL语句&#xff1b;将其中的 CESHI 替换为要创建的用户名即可&#xff0c;默认创建了数据表空间&#xff0c;索引表空间&#xff0c;文件大…...

Thread类中run和start的区别

答&#xff1a;调用线程类中的 start 方法&#xff0c;才开始创建并启动线程&#xff0c;而线程被回收&#xff0c;则是要执行完线程的入口方法&#xff08;对于主线程来说&#xff0c;则是要执行完 main 方法&#xff09;&#xff0c;这里要回收线程则是要将&#xff08;&…...

ElementUI浅尝辄止35:Checkbox 多选框

一组备选项中进行多选 1.如何使用&#xff1f; 单独使用可以表示两种状态之间的切换&#xff0c;写在标签中的内容为 checkbox 按钮后的介绍。 //在el-checkbox元素中定义v-model绑定变量&#xff0c;单一的checkbox中&#xff0c;默认绑定变量的值会是Boolean&#xff0c;选…...

讲讲如何用IDEA开发java项目——本文来自AI创作助手

使用IDEA开发Java项目&#xff0c;您可以按照以下步骤进行操作&#xff1a; 下载并安装IntelliJ IDEA 您可以从JetBrains官网下载并安装最新版的IntelliJ IDEA。 创建项目 启动IDEA&#xff0c;在欢迎界面中选择“Create New Project”或者在主菜单中选择“File”->“Ne…...

Kafka3.0.0版本——消费者(Range分区分配策略以及再平衡)

目录 一、Range分区分配策略原理1.1、Range分区分配策略原理的示例一1.2、Range分区分配策略原理的示例二1.3、Range分区分配策略原理的示例注意事项 二、Range 分区分配策略代码案例2.1、创建带有4个分区的fiveTopic主题2.2、创建三个消费者 组成 消费者组2.3、创建生产者2.4、…...

WeiTools

目录 1.1 WeiTools 1.2 getTime 1.3 getImageView 1.4 StringEncode 1.4.1 // TODO Auto-generated catch block WeiTools package com.shrimp.xiaoweirobot.tools;...

目标检测数据集:医学图像检测数据集(自己标注)

1.专栏介绍 ✨✨✨✨✨✨目标检测数据集✨✨✨✨✨✨ 本专栏提供各种场景的数据集,主要聚焦:工业缺陷检测数据集、小目标数据集、遥感数据集、红外小目标数据集,该专栏的数据集会在多个专栏进行验证,在多个数据集进行验证mAP涨点明显,尤其是小目标、遮挡物精度提升明显的…...

【系统设计系列】数据库

系统设计系列初衷 System Design Primer&#xff1a; 英文文档 GitHub - donnemartin/system-design-primer: Learn how to design large-scale systems. Prep for the system design interview. Includes Anki flashcards. 中文版&#xff1a; https://github.com/donnemarti…...

mp4压缩视频不改变画质?跟我这样压缩视频大小

在当今数字化时代&#xff0c;视频文件变得越来越普遍&#xff0c;然而&#xff0c;这些文件通常都很大&#xff0c;给存储和传输带来了困难&#xff0c;为了解决这个问题&#xff0c;许多人都希望将视频压缩得更小&#xff0c;而又不牺牲画质&#xff0c;下面就来看看具体应该…...

AQS同步队列和等待队列的同步机制

理解AQS必须要理解同步队列和等待队列之间的同步机制&#xff0c;简单来说流程是&#xff1a; 获取锁失败的线程进入同步队列&#xff0c;成功的占用锁&#xff0c;占锁线程调用await方法进入条件等待队列&#xff0c;其他占锁线程调用signal方法&#xff0c;条件等待队列线程进…...

vue3实现无限循环滚动的方法;el-table内容无限循环滚动的实现

需求&#xff1a;vue3实现一个div内的内容无限循环滚动 方法一&#xff1a; <template><div idcontainer><div class"item" v-foritem in 5>测试内容{{{ item }}</div></div> </template><script setup> //封装一个方法…...

Windows 安装 MariaDB 数据库

之前一直使用 MySQL&#xff0c;使用 MySQL8.0 时候&#xff0c;占用内存比较大&#xff0c;储存空间好像也稍微有点大&#xff0c;看到 MariaDB 是用来代替 MySQL 的方案&#xff0c;之前用着也挺得劲&#xff0c;MySQL8.0 以上好像不能去导入低版本的 sql&#xff0c;或者需要…...

RK3568-mpp(Media Process Platform)媒体处理软件平台

第一章 MPP 介绍 1.1 概述 瑞芯微提供的媒体处理软件平台(Media Process Platform,简称 MPP)是适用于瑞芯微芯片系列的通用媒体处理软件平台。 该平台对应用软件屏蔽了芯片相关的复杂底层处理,其目的是为了屏蔽不同芯片的差异,为使用者提供统一的视频媒体处理接口(Medi…...

【ModelSim】使用终端命令行来编译、运行Verilog程序,创建脚本教程

▚ 01 ModelSim命令解说 &#x1f4e2; 这些命令是 ModelSim 中常用的命令&#xff0c;用于创建库、编译源代码和启动仿真。 &#x1f514; 在使用这些命令之前&#xff0c;你需要在 ModelSim 的命令行界面或脚本中执行 vlib 命令来创建一个库&#xff0c;然后使用 vlog 命令…...

腾讯云网站备案详细流程_审核时间说明

腾讯云网站备案流程先填写基础信息、主体信息和网站信息&#xff0c;然后提交备案后等待腾讯云初审&#xff0c;初审通过后进行短信核验&#xff0c;最后等待各省管局审核&#xff0c;前面腾讯云初审时间1到2天左右&#xff0c;最长时间是等待管局审核时间&#xff0c;网站备案…...

HTTP介绍:一文了解什么是HTTP

前言&#xff1a; 在当今数字时代&#xff0c;互联网已经成为人们生活中不可或缺的一部分。无论是浏览网页、发送电子邮件还是在线购物&#xff0c;我们都离不开超文本传输协议&#xff08;HTTP&#xff09;。HTTP作为一种通信协议&#xff0c;扮演着连接客户端和服务器的重要角…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...