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; }
|