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

MekakuCityActors

于 2019-10-17 18:03:08 发布

阅读量370

点赞数 1

分类专栏：树hash 文章标签：树的同构树hash

本文链接：https://blog.csdn.net/IS_project/article/details/102612104

版权

这篇博客介绍了如何解决树同构问题，主要方法包括树哈希和最小表示法。通过树哈希，对于有根树从根节点开始计算哈希值，无根树则找到重心作为根节点进行哈希。文中提供了使用特定哈希方程的代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

P5043 【模板】树同构（[BJOI2015]树的同构）
题意：输出与第i棵树同构的树的最小编号

题解：树hash或者最小表示法
树hash，有根树直接从根结点开始hash即可，对于无根树，由于每棵树的重心最多有两个，所以找到重心当作根节点开始hash即可。
我这里采用的hash方程为

    sort(g.begin(),g.end());
    for(int i=0;i<g.size();i++){
   
        ac[u]=(ac[u]*base%mod+g[i])%mod;
    }
    ac[u]=(ac[u]*siz[u])%mod;

完整代码

#include<bits/stdc++.h>

using namespace std;
#define debug(x) cout<<#x<<" is "<<x<<endl;
typedef long long ll;

const int maxn=105;
const int inf=1e9+5;
const int mod=23333;
const int base=233;

struct edge{
   
    int fr;
    int to;
    int nex;
}e[maxn<<1

最低0.47元/天解锁文章