树哈希

乱搞。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000006;
const __uint128_t P = 0xffffffff00000001;
int n;
const __uint128_t B = 19260817;
__uint128_t BASE[MAXN];
__uint128_t RAND[MAXN][4];
struct Graph {
#define forGraph(u, v) for (int i = fst[u], v = to[i]; i; i = nxt[i], v = to[i])
    int fst[MAXN], nxt[MAXN << 1], to[MAXN << 1], tot;
    int siz[MAXN];
    __uint128_t f1[MAXN], f2[MAXN];
    void add(int u, int v) {
        to[++tot] = v, nxt[tot] = fst[u], fst[u] = tot;
    }
    void dfs(int u, int pre) {
        vector<int> q;
        siz[u] = 1;
        forGraph(u, v) if (v != pre) {
            dfs(v, u);
            q.push_back(v);
            siz[u] += siz[v];
        }
        sort(begin(q), end(q), [&](int a, int b) { return f1[a] < f1[b]; });
        f1[u] = RAND[siz[u]][0];
        f2[u] = RAND[siz[u]][2];
        for (auto v : q) {
            f1[u] = (1ll * f1[u] * BASE[siz[v]] + f2[v]) % P;
            f2[u] = ((1ll * f2[u] * BASE[siz[v]]) ^ f1[v]) % P;
			// 《交叉哈希》
        }
        f1[u] = (1ll * f1[u] * B + RAND[siz[u]][1]) % P;
        f2[u] = (1ll * f2[u] * B + RAND[siz[u]][3]) % P;
    }
} g;
int main() {
    BASE[0] = 1;
    mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
    for (int i = 1; i < MAXN; i++) BASE[i] = 1ll * BASE[i - 1] * B % P;
    for (int j = 0; j < 4; j++) {
        for (int i = 1; i < MAXN; i++) RAND[i][j] = Rand() % P;
    }
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int a, b; scanf("%d%d", &a, &b);
        g.add(a, b), g.add(b, a);
    }
    g.dfs(1, 0);
    set<pair<__uint128_t, __uint128_t>> s;
    for (int i = 1; i <= n; i++) s.insert({ g.f1[i], g.f2[i] });
    printf("%lu\n", s.size());
    return 0;
}

有没有大佬能把这个卡掉啊