Tree Isomorphism - YessineJallouli/Competitive-Programming GitHub Wiki

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5+7;
int subTreeSize[N];
 
long long ans;
int n;
 
map<vector<int>, int> mp;
 
int hsh(vector<vector<int>> &tree, int node, int par = -1) {
    vector<int> id;
    for (int u : tree[node]) {
        if (u != par) {
            id.emplace_back(hsh(tree, u, node));
        }
    }
    sort(id.begin(), id.end());
    if (mp.find(id) == mp.end()) {
        mp[id] = (int)mp.size();
    }
    return mp[id];
}
 
vector<int> centroids;
 
void get_centroid(vector<vector<int>> &tree, int node, int par = -1) {
    bool ok = true;
    int sum = 1;
    subTreeSize[node] = 1;
    for (int i : tree[node]) {
        if (i != par) {
            get_centroid(tree, i, node);
            subTreeSize[node]+= subTreeSize[i];
            sum+= subTreeSize[i];
            if (subTreeSize[i]*2 > n)
                ok = false;
        }
    }
    int last = n-sum;
    if (ok && last*2 <= n)
        centroids.push_back(node);
}
 
void init() {
    centroids.clear();
}
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        mp.clear();
        cin >> n;
        vector<vector<int>> tree1(n+1), tree2(n+1);
        for (int i = 0; i < n-1; i++) {
            int a,b; cin >> a >> b;
            tree1[a].push_back(b);
            tree1[b].push_back(a);
        }
        for (int i = 0; i < n-1; i++) {
            int a,b; cin >> a >> b;
            tree2[a].push_back(b);
            tree2[b].push_back(a);
        }
        get_centroid(tree1, 1);
        init();
        long long ans = hsh(tree1, centroids[0]);
        init();
        get_centroid(tree2, 1);
        bool ok = false;
        for (int v : centroids) {
            init();
            int ans1 = hsh(tree2,v);
            if (ans1 == ans)
                ok = true;
        }
        if (ok)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}