树哈希 Tree Hash

xiezheyuan · 2024-03-05 13:20:30 · 算法·理论

简介

树哈希是一种对树映射到一个数的方法。由于是哈希方法，所以做不到一一映射。只能做到反满射（我随便取的一个名字）。

主要用于解决树同构相关问题。两棵树同构，当且仅当点数相同，且可以将一棵树重新标号，使得这两棵树完全相同。

有根树哈希

参考了一种好写且卡不掉的树哈希的实现方法。

设 f(x) 为此树中以 x 为根的子树的哈希值。则我们可以定义：

f(x)=G\left(\sum_{v\in\text{son}(u)}F(f(v))\right)

其中 F,G 使我们定义的两个函数。

一般来说，F 是某一个整数到整数的映射，可以用多项式混合异或+位移（学名叫 xor-shift）的方法。而 G 主要用于限制 f 的大小，一般可以用取模。但是如果只有取模则所有哈希值均为零，所以可以改成加上一个常数然后取模。

然后我们一遍 dfs 就可以求出来所有子树的哈希值。

UOJ 763. 树哈希

给出一个 n 个点的树，你需要选择若干个子树，使得两两不同构，最大化选择子树数量。

考虑求出所有子树的树哈希，因为树哈希和编号无关，则哈希值相同大概率是同构的，则可以用 set 维护树哈希即可。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

set<ull> sset;
const int N = 1e6 + 5;

struct edge{
    int nxt,to;
} g[N << 1];
int head[N], ec;
mt19937_64 rnd;
ull C, f[N], val;

ull magic(ull x){
    x ^= val;
    x ^= (x >> 5);
    x ^= (x << 3);
    x ^= (x >> 9);
    x ^= (x << 3);
    return x + 1145141919810893ull;
}

void add(int u, int v){
    g[++ec].nxt=head[u];
    g[ec].to=v;
    head[u] = ec;
}

void dfs(int u, int fa){
    f[u] = 0;
    for(int i=head[u];i;i=g[i].nxt){
        int v = g[i].to;
        if(v == fa) continue;
        dfs(v, u);
        f[u] += magic(f[v]);
    }
    f[u] += C;
//  cout<<u<<' '<<f[u]<<'\n';
    sset.insert(f[u]);
}

int n;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    rnd.seed(chrono::steady_clock::now().time_since_epoch().count());
    C = rnd();val = rnd();
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        add(u, v);add(v, u);
    }
    dfs(1, 0);
    cout<<sset.size();
    return 0;
}

无根树哈希

考虑到我们构造的哈希函数是一个求和的形式，我们可以考虑换根 dp，求出以每一个点为根时的哈希值。然后你可以钦定最大 / 最小的为哈希值（如果你愿意，中位数、平均值也行）。

P5043 【模板】树同构（[BJOI2015]树的同构）

给定 m 棵树，每棵树有一个编号。对于每一棵树，输出最小的与它重构的树的编号。

我们钦定每棵树中，每个节点为根的情况中哈希值最大的那个定义为它的哈希值。然后把哈希值插到 map 去维护即可。

// 省略部分代码

int m, n;
ull f2[N];

void dfs2(int u, int fa){
    for(int i=head[u];i;i=g[i].nxt){
        int v = g[i].to;
        if(v == fa) continue;
        f2[v] = f[v] + magic(f2[u] - magic(f[v]));
        dfs2(v, u);
    }
}

map<int,int> mmap[N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>m;
    rnd.seed(chrono::steady_clock::now().time_since_epoch().count());
    C = rnd();val = rnd();
    for(int T=1;T<=m;T++){
        int n;
        cin>>n;
        for(int i=1,u;i<=n;i++){
            cin>>u;
            if(u != 0) add(u, i), add(i, u);
        }
        dfs(1, 0);
        f2[1] = f[1];
        dfs2(1, 0);
        int hsh = *max_element(f2+1, f2+n+1);
        if(mmap[n].count(hsh)) cout<<mmap[n][hsh]<<'\n';
        else{
            cout<<T<<'\n';
            mmap[n][hsh] = T;
        }
        memset(g, 0, sizeof(g));
        memset(head, 0, sizeof(head));
        ec = 0;
    }
    return 0;
}

SPOJ TREEISO - Tree Isomorphism

题解

习题

P4323 [JSOI2016] 独特的树叶

JYY 有两棵树 A 和 B ：树 A 有 N 个点，编号为 1 到 N ；树 B 有 N+1 个节点，编号为 1 到 N+1

JYY 知道树 B 恰好是由树 A 加上一个叶节点，然后将节点的编号打乱后得到的。他想知道，这个多余的叶子到底是树 B 中的哪一个叶节点呢？

首先按照我们的哈希方式，如果我们强制钦定叶子为根，如何求出删掉根节点之后的树的哈希？容易发现减去那个常数之后，就是 shift 后的树哈希。所以我们把 A 树最后得到的树哈希也 shift 一下就好了。最后我们不知道删去这个叶子在什么位置，所以你需要换根之后插到一个 set 里去维护。

// 省略部分代码

set<ull> sset;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    rnd.seed(chrono::steady_clock::now().time_since_epoch().count());
    C = rnd();val = rnd();
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        add(u, v);add(v, u);
    }
    dfs(1, 0);
    f2[1] = f[1];
    dfs2(1, 0);
    for(int i=1;i<=n;i++) sset.insert(magic(f2[i]));
    memset(g, 0, sizeof(g));
    memset(head, 0, sizeof(head));
    ec = 0;
    for(int i=1,u,v;i<=n;i++){
        cin>>u>>v;
        add(u, v);add(v, u);
    }
    dfs(1, 0);
    f2[1] = f[1];
    dfs2(1, 0);
    for(int i=1;i<=n;i++){
        if(sset.find(f2[i] - C) != sset.end()){
            cout<<i;
            return 0;
        }
    }
    return 0;
}