学习笔记——树上哈希

这篇具有很好参考价值的文章主要介绍了学习笔记——树上哈希。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

普通子树哈希

树上的很多东西都是转化成链上问题的,比如树上哈希
树上哈希,主要是用于树的同构这个东西上的
什么是树的同构?
学习笔记——树上哈希,哈希算法,学习,笔记
如图,不考虑节点编号,三棵树是同构的

将树转化成链,一般有两种方式:环游欧拉序与欧拉序
为了尽可能减少哈希冲突,进制位越小越好
又因为不考虑节点编号,很明显,若是采用欧拉序的话,得要记录该节点孩子数
环游欧拉序只用进入打上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)统计答案
题目就这么结束了文章来源地址https://www.toymoban.com/news/detail-704038.html

代码

#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;
    do
        ch[++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;
        else
            r = mid - 1;
    }
    printf("%llu\n", l);
}

到了这里,关于学习笔记——树上哈希的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 密码学学习笔记(二十三):哈希函数的安全性质:抗碰撞性,抗第一原象性和抗第二原象性

    在密码学中,哈希函数是一种将任意长度的数据映射到固定长度输出的函数,这个输出通常称为哈希值。理想的哈希函数需要具备几个重要的安全性质,以确保数据的完整性和验证数据的来源。这些性质包括抗碰撞性、抗第一原象性和抗第二原象性。 抗碰撞性指的是在合理的

    2024年02月05日
    浏览(54)
  • 区块链:哈希算法与一致性哈希算法

    本篇主要介绍区块链中常用到的哈希算法。 1 哈希算法 1.1 定义及特性   哈希算法是指通过哈希函数(Hash Function)对任意长度的输入数据(比如文件、消息、数字等)进行转换,生成一个固定长度的哈希值(Hash Value)的过程。   在区块链中,哈希算法常用于区块验证及安全性保

    2024年02月17日
    浏览(64)
  • (学习笔记-调度算法)进程调度算法

    进程调度算法也称 CPU 调度算法,毕竟进程是由 CPU 调度的。 当 CPU 空闲时,操作系统就选择内存中标的某个 [就绪状态] 的进程,将其分配给 CPU。 什么时候会发生CPU调度呢?通常有以下情况: 当进程从运行状态转换到等待状态 当进程从运行状态转换到就绪状态 当进程从等待

    2024年02月11日
    浏览(42)
  • 哈希算法--MD5算法

    哈希算法也称摘要算法、散列算法,哈希函数的输入为一段 可变长度x ,输出一 固定长度串 ,该串被称为 x的哈希值 。 Hash函数满足以下几个基本需求: (1)输入值x为任意长度 (2)输出值长度固定 (3)单向函数,算法不可逆 (4)唯一性,很难找到两个不同的输入会得到

    2023年04月18日
    浏览(73)
  • 算法设计与分析学习笔记之二分查找算法

    二分查找只适用于有序的顺序表,非严格递增或是非严格递减都行。 二分查找运用到了分治的思想,将整体逐渐分为许多个小的部分,让整体的解变为诸多小部分解的合成,要求整体可以分解,小部分的解汇合之后可以得到整体部分的解。 至此,结束。 如果你觉得这篇文章

    2024年02月09日
    浏览(46)
  • 【嵌入式算法】学习笔记(一):数字滤波算法

    最近在做直流电机的毕设中,由于需要采集转速,电流,电压,温度等参数,常规的采集容易受到干扰,所以特意复习了一下关于数字滤波有关的知识,并作出相应的整理。 本文对数字滤波进行简单介绍,讲解七种常用的滤波算法并用C语言实现,并比较其优缺点 。由于篇幅

    2023年04月22日
    浏览(97)
  • 【SM3哈希算法】算法原理

    参考: SM3算法是一种密码散列函数标准,由国家密码管理局发布。它的安全性和SHA-256相当,适用于商用密码应用中的数字签名和验证、消息认证码生成和验证、随机数生成等。 将输入的消息分成512位的分组,并对每个分组进行填充、分组、扩展、迭代压缩等操作,最后输出

    2024年02月08日
    浏览(42)
  • 【数据结构与算法】哈希—— 位图 | 布隆过滤器 | 哈希切割

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 哈希是一种映射思想,这里再讲解两种应用哈希思想的数据结构。 问题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数

    2024年02月02日
    浏览(57)
  • 进阶搜索算法 学习笔记

    DATE 20231031:补充一道好题 P4872 OIer们的东方梦(Dijkstra 分层图最短路)。 双向广搜、双向深搜 堆优化的 Dijkstra 一颗小小的 A-STAR 不大聪明的 IDDFS(IDS) 可爱的 IDA-STAR 这是进阶搜索算法,不说了直接上例题: 以“P1514 引水问题”为例: 点击查看代码 算法思想 在搜索的时候

    2024年02月09日
    浏览(45)
  • Manacher算法学习笔记

    Manacher算法就是马拉车。 Manacher算法就是用于解决回文子串的个数的。 P3805:【模板】manacher 算法 给出一个只由小写英文字符 (texttt a,texttt b,texttt c,ldotstexttt y,texttt z) 组成的字符串 (S) ,求 (S) 中最长回文串的长度。 为了找到最长的回文串的长度,我们首先就要考虑如何

    2024年02月09日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包