[BZOJ 4337 BJOI 2015 나무의 동구] 나무 해시.

[BZOJ 4337 BJOI 2015 나무의 동구] 나무 해시.
분류: Data Structure Hash template1. 제목 링크
[BZOJ 4337 BJOI 2015 나무의 동 구성]
2. 제목 설명
설명 트 리 는 흔히 볼 수 있 는 데이터 구조 이다.우 리 는 N 개의 점, N - 1 개의 변 의 연결 무 방향 도 를 나무 라 고 부른다.어떤 점 을 뿌리 로 하고 뿌리 부터 옮 겨 다 니 면 다른 점 은 모두 전구 가 있 고 이 나 무 는 뿌리 가 있 는 나무 가 된다.두 나무 T1 과 T2 에 대해 나무 T1 의 모든 점 을 다시 표시 하여 나무 T1 과 나무 T2 를 똑 같이 만 들 수 있다 면 이 두 나 무 는 같은 구조 이다.같은 형 태 를 갖 고 있다 는 얘 기다.지금, 당신 에 게 M 개의 나무 가 있 습 니 다. 그것들 을 같은 구조 관계 에 따라 몇 개의 등가 류 로 나 누 어 주세요.Input 첫 줄, 정수 M.다음 M 줄 은 줄 마다 몇 개의 정 수 를 포함 하고 나 무 를 표시 합 니 다.첫 번 째 정수 N 은 점 수 를 나타 낸다.다음 N 개의 정 수 는 번호 가 1 에서 N 인 각 점 의 아버지 결점 의 번 호 를 차례대로 나타 낸다.뿌리 노드 의 아버지 노드 번 호 는 0 이다.Output 출력 M 줄 은 줄 마다 하나의 정수 로 모든 트 리 와 같은 구조의 트 리 의 최소 번 호 를 표시 합 니 다.데이터 범위: 100% 데이터 중 1 ≤ N, M ≤ 50.
3. 문제 풀이 사고방식
트 리 해시 템 플 릿 문제 입 니 다.
4. 구현 코드

#include 
using namespace std;

typedef long long ll;
typedef long double lb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair pll;
typedef pair puu;
typedef pair pbb;
typedef vector<int> vi;

const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const long double PI = acos(-1.0);
const long double eps = 1e-4;
template<typename T> inline void umax(T &a, T b) { a = max(a, b); }
template<typename T> inline void umin(T &a, T b) { a = min(a, b); }

void debug() { cout << endl; }
template<typename T, typename ...R> void debug (T f, R ...r) { cout << "[" << f << "]"; debug (r...); }

const int MAXN = 100;
const int MAXE = 200;

ull qz[MAXN];

struct Tree {
    struct Edge {
        int v, next;
    } edge[MAXE];
    int n, head[MAXN], tot, root;
    ull h[MAXN];
    void init() {
        tot = 0;
        memset(head, -1, sizeof(head));
    }
    inline void add_edge(int u, int v) {
        edge[tot] = Edge{v, head[u]};
        head[u] = tot ++;
    }
    void read() {
        scanf("%d", &n);
        int fa;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &fa);
            if (fa == 0) root = i;
            else {
                add_edge(fa, i);
                add_edge(i, fa);
            }
        }
    }
    int siz[MAXN], mx_sum, g[MAXN], g_cnt;
    void dfs(int u, int fa) {
        int v, temp = 0;
        siz[u] = 1;
        for (int i = head[u]; ~i; i = edge[i].next) {
            v = edge[i].v;
            if (v == fa) continue;
            dfs(v, u);
            siz[u] += siz[v];
            umax(temp, siz[v] + 1);
        }
        umax(temp, n - siz[u] + 1);
        if (temp < mx_sum) {
            mx_sum = temp;
            g_cnt = 0;
            g[g_cnt ++] = u;
        } else if (mx_sum == temp) {
            g[g_cnt ++] = u;
        }
    }
    void hash_dfs(int u, int fa) {
        int v;
        h[u] = siz[u] = 1;
        for (int i = head[u]; ~i; i = edge[i].next) {
            v = edge[i].v;
            if (v == fa) continue;
            hash_dfs(v, u);
            h[u] += h[v] ^ qz[siz[v]];
            siz[u] += siz[v];
        }
        h[u] *= qz[n - siz[u] + 1];
    }
    ull hashV() {
        mx_sum = INF; g_cnt = 0;
        dfs(root, 0);
        ull hv = 1;
        for(int i = 0; i < g_cnt; ++i) {
            hash_dfs(g[i], 0);
            hv *= h[g[i]];
        }
        return hv;
    }
} tr;

int main() {
#ifdef ___LOCAL_WONZY___
    freopen ("input.txt", "r", stdin);
#endif // ___LOCAL_WONZY___
    for (int i = 0; i < MAXN; ++i) qz[i] = (ull) rand() * rand();
    int m;
    while (~scanf("%d", &m)) {
        mapint> mp;
        for (int i = 1; i <= m; ++i) {
            tr.init();
            tr.read();
            ull hv = tr.hashV();
            if (!mp[hv]) mp[hv] = i;
            printf("%d
", mp[hv]);
        }
    }
#ifdef ___LOCAL_WONZY___
    cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif // ___LOCAL_WONZY___
    return 0;
}