小水题一种hash树的规则, 还是记一下.

对于一个点的直属儿子, 将它们的哈希值排序, 依次乘以不太小(50+)的素数并求和.

以每个点为根求hash值, 判同构就$n^2$比对了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxm = 5005;

struct edge {
  int to, nxt;
}e[maxm];
int m;
int n[55];
int pr[55], npr[505], cnt;
int ptr, lnk[55];
ll h[55], arr[55][55];

inline void add(int bgn, int end) {
  e[++ptr] = (edge){end, lnk[bgn]};
  lnk[bgn] = ptr;
}
void euler() {
  for (int i = 2; i <= 500; ++i) {
    if (!npr[i]) pr[++cnt] = i;
    for (int j = 1; j <= cnt && i * pr[j] <= 500; ++j) {
      npr[i * pr[j]] = 1;
      if (!(i % pr[j])) break;
    }
  }
  int j, w = 0;
  for (j = 1; pr[j] <= 50; ++j);
  for (; j <= cnt; ++j) {
    pr[++w] = pr[j];
  }
}
void dfs(int x, int fa) {
  vector<int> vec; vec.push_back(1);
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == fa) continue;
    dfs(y, x);
    vec.push_back(h[y]);
  }
  h[x] = 0; sort(vec.begin(), vec.end());
  for (int j = 0; j < (int)vec.size(); ++j) {
    h[x] += vec[j] * pr[j + 1];
  }
}

int main() {
  scanf("%d", &m);
  euler();
  for (int i = 1; i <= m; ++i) {
    ptr = 0; memset(lnk, 0, sizeof lnk);
    scanf("%d", &n[i]); int u;
    for (int j = 1; j <= n[i]; ++j) {
      scanf("%d", &u);
      if (u) add(u, j), add(j, u);
    }
    for (int j = 1; j <= n[i]; ++j) {
      dfs(j, 0);
      arr[i][j] = h[j];
    }
    sort(arr[i] + 1, arr[i] + 1 + n[i]);
    for (int k = 1; k <= i; ++k) {
      bool sol = true;
      for (int p = 1; p <= n[i]; ++p) {
        if (arr[i][p] != arr[k][p]) {
          sol = false;
          break;
        }
      }
      if (sol) {
        printf("%d\n", k);
        break;
      }
    }
  }

  return 0;
}