History Lesson

Let's take a look at the solve count for the last problems in the last 4 division 2 contests:

803 (Div. 2): F (7 official solves); G (2 official solve)

802: E (18 official solves): F (11 official solves)

801: E (1 official solve)

Edu 130: F (2 official solves)

There's a trend. The last and hardest div2 problem frequently has very few official solves. This means that the last problem, despite taking a lot of time to create, doesn't really affect rankings that much. The authors spent much time for a problem that didn't make a big difference. But it would've made a difference in div1.

Personally, I think that it's okay if 20 or even 30 people AK a div2 round, so it's okay to have 20-30 people solving the last problem. Then, you can take those hard problems and insert them into a div1 round. That way, we can have more contests.

Basically, make div2 last problems a little easier, that way we can save those hard problems for another contest.

What do you think?

Introduction

I have no school right now, and there's no tutorials on Tree Isomorphism on Codeforces, so I decided to write one :).

What is a tree isomorphism?

Maybe you recognize the word isomorphic: in the context of abstract algebra when two objects are effectively the same, but are labelled differently. We can extend this to trees as well: two trees are isomorphic if they are the same, but may have different node labels. For example,

are isomorphic because we can relabel the nodes. If you want a more rigorous definition, then two trees $$$T_1 = (V_1, E_1)$$$ and $$$T_2 = (V_2, E_2)$$$ are isomorphic iff there exists a $$$\phi$$$ for which $$$\phi(E_1) = E_2$$$ and a $$$\phi^{-1}$$$ for which $$$\phi^{-1} (E_2) = E_1$$$.

What is the problem?

We want to determine if two unrooted trees are isomorphic in $$$\mathcal{O}(N \log N)$$$ time.

If we can solve the problem for rooted trees, can we solve it for unrooted trees?

Yes. We can transform our original problem of checking if two trees are isomorphic into checking if two rooted trees are isomorphic easily. How? We can find the centroids of our first tree and our centroids of our second tree, and then root them at their centroids. So now, we have transformed our unrooted case into a rooted case.

Heuristics

You can skip this, if you'd like. I'm just going to list out some ideas for tree isomorphism checking. All of the following ideas won't solve the problem, but some of them work decently well.

Idea 1: Find the degrees of all nodes and check if $$$\text{oc}_{T1}[i] = \text{oc}_{T2}[i]$$$, where $$$\text{oc}_{T}[i]$$$ is the number of vertices of degree $$$i$$$. If $$$\text{oc}_{T1}[i] = \text{oc}_{T2}[i] \forall i$$$ does not hold, then we know that the trees are not isomorphic.

Idea 2: Root the trees at their centroids. $$$\text{oc}_{T1}[i] = \text{oc}_{T2}[i]$$$, where $$$\text{oc}_{T}[i]$$$ is the number of vertices with subtree size $$$i$$$. If $$$\text{oc}_{T1}[i] = \text{oc}_{T2}[i] \forall i$$$ does not hold, then we know that the trees are not isomorphic.

Idea 3: If the diameters of the tree are not the same, then they cannot be isomorphic.

Idea 4: We know that for fixed $$$k$$$, the number of paths of length $$$k$$$ must be the same in both trees.

If we merge all of the ideas together, we will get a pretty good heuristic and will be able to identify with pretty good accuracy if a tree is isomorphic to another tree. But that's not good enough.

The idea

The idea is to parenthesize our tree. We can recursively, say that:

where $$$+$$$ denotes string concatenation. But obviously, the string parenthesization for rooted trees do not always yield the same result, even for isomorphic trees:

So what can we do? It turns out, we can just "order" the parenthesization. That is, concactenate in increasing or decreasing order of the string parenthesization.

How would it look like if we did that?

So, in short, the idea is to parenthesize the tree and then concactenate in some fixed order (one easy way is in increasing order of the strings).

But that's $$$\mathcal{O}(N^2)$$$, since we're dealing with a lot of potentially large strings. No problem! We can replace each opening parenthesis with a $$$1$$$ and each closing parenthesis with a 0. For example, $$$(()())$$$ would become $$$110100$$$. We can then convert the binary string to a number, by using it's binary representation. In the case that the number is too large, we can take it modulo some large prime $$$p$$$.

The end.

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <limits.h>
 
using namespace std;
const int MOD = 1e9 + 9;
 
class Tree {
public:
    vector<vector<int>> adj;
    vector<int> centroid;
    vector<int> sub;
    vector<int> id;
    vector<int64_t> powr;
 
    void dfs(int curNode, int prevNode) {
        sub[curNode] = 1;
        bool is_centroid = true;
        vector<pair<int, int>> nodes;
        for (int v: adj[curNode]) {
            if (v != prevNode) {
                dfs(v, curNode);
                sub[curNode] += sub[v];
                if (sub[v] > (int) adj.size() / 2) {
                    is_centroid = false;
                }
                nodes.emplace_back(id[v], v);
            }
        }
        sort(nodes.begin(), nodes.end());
        id[curNode] = 1;
        for (auto& p: nodes) {
            id[curNode] = ((powr[sub[p.second] + 1] * id[curNode]) % MOD + id[p.second]) % MOD;
        }
        id[curNode] *= 2;
        id[curNode] %= MOD;
        if ((int) adj.size() - sub[curNode] > (int) adj.size() / 2) {
            is_centroid = false;
        }
        if (is_centroid) {
            centroid.push_back(curNode);
        }
    }
 
    vector<int> Centroid() {
        dfs(0, -1);
        return centroid;
    }
 
    bool isIsomorphic(int root1, Tree t2, int root2) {
        dfs(root1, root1);
        t2.dfs(root2, root2);
        sort(sub.begin(), sub.end());
        sort(t2.sub.begin(), t2.sub.end());
        return (id[root1] == t2.id[root2]);
    }
 
    void add_edge(int u, int v) {
        adj[u].push_back(v), adj[v].push_back(u);
    }
 
    Tree(int n) {
        adj.resize(n);
        sub.resize(n);
        id.resize(n);
        powr.resize(n + 1);
        powr[0] = 1;
        for (int i = 1; i <= n; i++) {
            powr[i] = 2 * powr[i - 1];
            powr[i] %= MOD;
        }
    }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int N;
        cin >> N;
        Tree t1(N), t2(N);
        for (int i = 0; i < N - 1; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            t1.add_edge(u, v);
        }
        for (int i = 0; i < N - 1; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            t2.add_edge(u, v);
        }
        vector<int> c1 = t1.Centroid();
        vector<int> c2 = t2.Centroid();
        bool done = false;
        for (int i: c1) {
            for (int j: c2) {
                if (!done && t1.isIsomorphic(i, t2, j)) {
                    cout << "YES\n";
                    done = true;
                    break;
                }
            }
        }
        if (!done) {
            cout << "NO\n";
        }
    }
}

URL to submit