TOI14: blockchain (Hashing)

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const int K = 10241024 + 10;
const lli PB = 98765431;
const int DG = 1e4;
unordered_map <lli, int> cnt;
lli pk[K];

int main(){

    int T, Q;
    scanf("%d%d", &T, &Q);

    pk[0] = 1;
    for(int i=1;i<=K-10;i++){
        pk[i] = pk[i-1] * PB;
    }

    for(int t=1;t<=T;t++){
        int n;
        scanf("%d", &n);
        lli hsh = 0;
        for(int i=1;i<n;i++){
            int u, v;
            scanf("%d%d", &u, &v);
            if(u > v) swap(u, v);
            hsh += pk[u * DG + v];
        }
        cnt[hsh] ++;
    }

    for(int q=1;q<=Q;q++){
        int n;
        scanf("%d", &n);
        lli hsh = 0;
        for(int i=1;i<n;i++){
            int u, v;
            scanf("%d%d", &u, &v);
            if(u > v) swap(u, v);
            hsh += pk[u * DG + v];
        }
        printf("%d\n", cnt[hsh]);
    }

    return 0;
}

/*
ระวัง (A, B) (C, D)
    (A, D) (C, B)
เก็บ u, v เป็นตัวเลข
เช่น u = 1024, v = 1024 -> 10241024
    u = 1,    v = 300  ->    10300
แล้วเอาไป hash เก็บทั้งหมดไว้
*/