https://csacademy.com/contest/round-73/task/binary-isomorphism/
(問題の意味が完全に理解できなかったけど、多分)
2つの根付き木が与えられるので同型判定せよ。
前提知識
解法
特に解説することも無いのだが、木の同型判定をするにはいくつか方法がある。
特にオススメなのが、ハッシュを使うrngさんのやり方である。参考
int getrandmax() { static uint32_t y = time(NULL); y ^= (y << 13); y ^= (y >> 17); y ^= (y << 5); return y; } int N; vector<int> E1[101010], E2[101010]; //--------------------------------------------------------------------------------------------------- int rnd[101010], mod = 1000000007, dpt[101010]; int dfs(int cu, vector<int> e[]) { vector<int> hashs; fore(to, e[cu]) { hashs.push_back(dfs(to, e)); chmax(dpt[cu], dpt[to] + 1); } ll ret = 1; fore(h, hashs) ret = (ret * (rnd[dpt[cu]] + h)) % mod; return ret; } //--------------------------------------------------------------------------------------------------- void solve() { cin >> N; rep(i, 0, N) { E1[i].clear(); E2[i].clear(); } int r1, r2; rep(i, 0, N) { int p; cin >> p; p--; if (0 <= p) { E1[p].push_back(i); } else r1 = i; } rep(i, 0, N) { int p; cin >> p; p--; if (0 <= p) { E2[p].push_back(i); } else r2 = i; } rep(i, 0, N) dpt[i] = 0; int h1 = dfs(r1, E1); rep(i, 0, N) dpt[i] = 0; int h2 = dfs(r2, E2); if (h1 == h2) printf("1\n"); else printf("0\n"); } //--------------------------------------------------------------------------------------------------- void _main() { rep(i, 0, 101010) rnd[i] = getrandmax(); int T; cin >> T; rep(t, 0, T) solve(); }