学习笔记——树上哈希
普通子树哈希
树上的很多东西都是转化成链上问题的,比如树上哈希
树上哈希,主要是用于树的同构这个东西上的
什么是树的同构?
如图,不考虑节点编号,三棵树是同构的
将树转化成链,一般有两种方式:环游欧拉序与欧拉序
为了尽可能减少哈希冲突,进制位越小越好
又因为不考虑节点编号,很明显,若是采用欧拉序的话,得要记录该节点孩子数
环游欧拉序只用进入打上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 k−1
于是,题目就这样转化成了求是否存在同构的 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);
}
相关文章:

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

Opencv快速入门教程,Python计算机视觉基础
快速入门 OpenCV 是 Intel 开源计算机视觉库。它由一系列 C 函数和少量 C 类构成, 实现了图像处理和计算机视觉方面的很多通用算法。 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自动化之混合框架
什么是混合框架,混合框架就是将数据驱动与关键字驱动结合在一起,主要用来回归业务主流程,将核心流程串联起来。 上一篇我们写到了关键字驱动框架,关键字驱动框架是针对一个业务场景的单条测试用例的。 我们以163邮箱的登录到创建…...
SQL创建用户-非DM8.2环境(达梦数据库)
DM8:达梦数据库SQL创建用户-非DM8.2环境 环境介绍 环境介绍 在没有图形化界面,或者想快速创建用户,可以使用一下SQL语句;将其中的 CESHI 替换为要创建的用户名即可,默认创建了数据表空间,索引表空间,文件大…...
Thread类中run和start的区别
答:调用线程类中的 start 方法,才开始创建并启动线程,而线程被回收,则是要执行完线程的入口方法(对于主线程来说,则是要执行完 main 方法),这里要回收线程则是要将(&…...
ElementUI浅尝辄止35:Checkbox 多选框
一组备选项中进行多选 1.如何使用? 单独使用可以表示两种状态之间的切换,写在标签中的内容为 checkbox 按钮后的介绍。 //在el-checkbox元素中定义v-model绑定变量,单一的checkbox中,默认绑定变量的值会是Boolean,选…...
讲讲如何用IDEA开发java项目——本文来自AI创作助手
使用IDEA开发Java项目,您可以按照以下步骤进行操作: 下载并安装IntelliJ IDEA 您可以从JetBrains官网下载并安装最新版的IntelliJ IDEA。 创建项目 启动IDEA,在欢迎界面中选择“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: 英文文档 GitHub - donnemartin/system-design-primer: Learn how to design large-scale systems. Prep for the system design interview. Includes Anki flashcards. 中文版: https://github.com/donnemarti…...

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

AQS同步队列和等待队列的同步机制
理解AQS必须要理解同步队列和等待队列之间的同步机制,简单来说流程是: 获取锁失败的线程进入同步队列,成功的占用锁,占锁线程调用await方法进入条件等待队列,其他占锁线程调用signal方法,条件等待队列线程进…...
vue3实现无限循环滚动的方法;el-table内容无限循环滚动的实现
需求:vue3实现一个div内的内容无限循环滚动 方法一: <template><div idcontainer><div class"item" v-foritem in 5>测试内容{{{ item }}</div></div> </template><script setup> //封装一个方法…...

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

RK3568-mpp(Media Process Platform)媒体处理软件平台
第一章 MPP 介绍 1.1 概述 瑞芯微提供的媒体处理软件平台(Media Process Platform,简称 MPP)是适用于瑞芯微芯片系列的通用媒体处理软件平台。 该平台对应用软件屏蔽了芯片相关的复杂底层处理,其目的是为了屏蔽不同芯片的差异,为使用者提供统一的视频媒体处理接口(Medi…...
【ModelSim】使用终端命令行来编译、运行Verilog程序,创建脚本教程
▚ 01 ModelSim命令解说 📢 这些命令是 ModelSim 中常用的命令,用于创建库、编译源代码和启动仿真。 🔔 在使用这些命令之前,你需要在 ModelSim 的命令行界面或脚本中执行 vlib 命令来创建一个库,然后使用 vlog 命令…...

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

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

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...