洛谷P5043 【模板】树同构（[BJOI2015]树的同构）题解

题目链接：P5043 【模板】树同构（[BJOI2015]树的同构）

题意：

树是一种很常见的数据结构。

我们把 $N$ 个点，$N-1$ 条边的连通无向图称为树。

若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。

对于两个树 $T_1$ 和 $T_2$，如果能够把树 $T_1$ 的所有点重新标号，使得树 $T_1$ 和树 $T_2$ 完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。

现在，给你 $M$ 个无根树，请你把它们按同构关系分成若干个等价类。

输入格式：

第一行，一个整数 $M$。

接下来 $M$ 行，每行包含若干个整数，表示一个树。第一个整数 $N$表示点数。接下来 $N$ 个整数，依次表示编号为 $1$ 到 $N$ 的每个点的父亲结点的编号。根节点父亲结点编号为 $0$。

输出格式：

输出 $M$ 行，每行一个整数，表示与每个树同构的树的最小编号。

数据范围：

$1\leq N,M\leq 50$。

考虑多项式哈希，记录 dfs 序。哈希值计算方式如下：

$\mathrm{hash}(u)= \mathrm{dep}(u)\cdot G^1 + \left(\mathrm{hash}(v_1)\cdot G^{1} + \mathrm{hash}(v_2)\cdot G^{1 + \mathrm{size}(v_1)} + \cdots\right)\quad\bmod P$

如果是有根树，且儿子有先后遍历顺序，那么这样哈希就是对的（为什么对我也不知道）。

如果子节点没有先后顺序，那就按照哈希值为第一关键字、子节点的子树大小为第二关键字排序后遍历。

不过题目是无根树，只需要找到重心把它当作根就好了。如果有两个重心，就比较两个哈希值。

时间复杂度 $\mathcal{O}(mn \log n)$ ，复杂度瓶颈是对哈希值排序。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int G = 131071;
const int mod = 998244353;
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(66))
#define Fi first
#define Se second

vector<int> vec[N]; pii tmp[N];
int n, rt, rrt, rt_sz, tot, sz[N], dep[N], hsh[N], pwd[N]; 
struct node { int a, b; } f[N];
bool operator==(node a, node b) { return a.a == b.a && a.b == b.b; }
void findrt(int u, int fa)
{
    sz[u] = 1; int mx = 0;
    for(int v : vec[u]) if(v != fa) {
        findrt(v, u); sz[u] += sz[v]; up(mx, sz[v]);
    }
    up(mx, n - sz[u]);
    if(mx < rt_sz) { rt_sz = mx, rt = u, rrt = 0; }
    else if(mx == rt_sz) { rrt = u; }
}
void dfs(int u, int fa)
{
    hsh[u] = dep[u] * pwd[1] % mod; sz[u] = 1;
    for(int v : vec[u]) if(v != fa) { dep[v] = dep[u] + 1; dfs(v, u); }
    tot = 0;
    for(int v : vec[u]) if(v != fa) { tmp[++tot] = {hsh[v], sz[v]}; }
    sort(tmp + 1, tmp + 1 + tot);
    for(int i = 1; i <= tot; i++)
    {
        hsh[u] += tmp[i].Fi * pwd[sz[u]] % mod;
        sz[u] += tmp[i].Se;
    }
}
void init(int id)
{
    cin >> n; rt_sz = n; rrt = 0;
    for(int i = 1; i <= n; i++) vec[i].clear();
    for(int i = 1, fa; i <= n; i++) {
        cin >> fa;
        if(fa) { vec[i].push_back(fa), vec[fa].push_back(i); }
    }
    findrt(1, 0); dep[rt] = 1; dfs(rt, 0); f[id].a = hsh[rt];
    if(rrt) { dep[rrt] = 1; dfs(rrt, 0); f[id].b = hsh[rrt]; }
    if(f[id].a < f[id].b) swap(f[id].a, f[id].b);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    pwd[0] = 1;
    for(int i = 1; i <= N - 5; i++) pwd[i] = pwd[i - 1] * G % mod;
    int m; cin >> m; for(int i = 1; i <= m; i++) init(i);
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= i; j++)
            if(f[i] == f[j]) { cout << j << '\n'; break; }
    return 0;
}