はまやんはまやんはまやん

hamayanhamayan's blog

Binary Isomorphism [CSAcademy #73 C]

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