AcWing - 157 - 树形地铁系统 = 树hash

https://www.acwing.com/problem/content/description/159/

树哈希千万不要用乘法，生成rand()的时候，以及进行哈希的时候都是，真的一个数有很多种因式分解的，冲突到飞起，还是移位然后异或比较实在。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ull ha[3005];

struct Tree {
    int root;
    vector<int> G[3005];
    int siz[3005];

    ull hashcode(int u) {
        siz[u] = 1;
        ull resu = 1;
        for(auto v : G[u]) {
            ull resv = hashcode(v);
            siz[u] += siz[v];
            resu ^= (resv ^ ha[siz[v]]) + siz[v];
        }
        return resu;
    }
} t1, t2;

char s1[3005], s2[3005];

int n1, id1, cur1;
void build1(int u) {
    while(s1[cur1] == '0') {
        int v = ++id1;
        t1.G[u].push_back(v);
        ++cur1;
        build1(v);
    }
    ++cur1;
    return;
}

int n2, id2, cur2;
void build2(int u) {
    while(s2[cur2] == '0') {
        int v = ++id2;
        t2.G[u].push_back(v);
        ++cur2;
        build2(v);
    }
    ++cur2;
    return;
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    srand(time(0));
    for(int i = 1; i <= 1501; ++i) {
        ha[i] = ((ull)rand() << 48) + ((ull)rand() << 32) + ((ull)rand() << 16) + (ull)rand();
    }

    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s%s", s1, s2);
        n1 = strlen(s1);
        n2 = strlen(s2);
        if(n1 != n2)
            puts("different");
        else {
            id1 = 1, cur1 = 0;
            for(int i = 0; i <= 3001; ++i) {
                t1.G[i].clear();
                t1.siz[i] = 0;
            }
            t1.root = 1;
            build1(id1);

            id2 = 1, cur2 = 0;
            for(int i = 0; i <= 3001; ++i) {
                t2.G[i].clear();
                t2.siz[i] = 0;
            }
            t2.root = 1;
            build2(id2);

            ull res11 = t1.hashcode(1);
            ull res12 = t2.hashcode(1);

            puts((res11 == res12) ? "same" : "different");
        }
    }
}

是真的异或最实在，非常快，还均匀，乱得不行。