### hitch_hiker42's blog

By hitch_hiker42, history, 6 weeks ago,

For context, I was solving this problem: https://cses.fi/problemset/task/1701, and was wondering if we can decompose the two trees into their respective centroid trees, and then compare their Euler tour sequence for bijection.

• +5

 » 6 weeks ago, # |   +12 Not necessarily, as for given a tree there could be two possible centroids so there are multiple possible centroid trees for a single tree. However, you're on the right track. Instead of actually creating the centroid tree, just root both trees at the centroids. If there are two in each tree, try both possibilities. Then, just check the trees for bijection. For more info, see this comment.
•  » » 6 weeks ago, # ^ |   0 can we check bijection using prufer code of the trees after rooting them onto their respective centroids?
•  » » » 6 weeks ago, # ^ |   0 AFAIK, no it's not possible as the Prüfer Code of a tree is generated using the labels on the nodes. You can see a description of a linear time algorithm to detect rooted tree isomorphism on page 2 here.
•  » » 6 weeks ago, # ^ | ← Rev. 8 →   +3 Thank you for the response, I read the paper in the given link and at first, struggled to understand it as it felt a little verbose but managed to do so after going through it about $2-3$ times. The algorithm was so elegant and smooth but felt a little ugly-ish while implementing as we needed to compare vectors lexicographically. Though, after implementing the AHU algorithm word-to-word, I realized that we might incorporate the structure of a subtree into a hash, and recursively compute the hash for a node from its children's hashes as follows: Sort the hashes of the children by value Run a polynomial hash, similar to one that we do for strings, over the children hashes by choosing a large prime as the multiplier, and another for the modulus. Though this is already a good hash function, it's still prone to rare collisions but we can improve the probability of no collisions by incorporating one random variable into the hash function and iterating the process $5-10$ times by changing the value of the random variable each time. The implementation gets easier significantly, compared to the naive adaptation of the AHU.Here are the two implementations for reference (both for the rooted version): 1. The naive AHU implementation //author: hitch_hiker42; #include using namespace std; //solution: #define int int64_t #define span(a) begin(a), end(a) constexpr int mxn = 1e5 + 1; struct tree { int n, lvl; vector> adj, level; vector label, parent; tree() = default; tree(int n): n(n), lvl(0) { adj.assign(n + 1, vector()); level.assign(n + 1, vector()); label.assign(n + 1, -1); parent.assign(n + 1, 0); } void insert(int u, int v) { adj[u].emplace_back(v); adj[v].emplace_back(u); } void dfs(int u, int p, int l) { level[l].emplace_back(u); parent[u] = p, lvl = max(lvl, l); for(auto& v: adj[u]) if(v != p) { dfs(v, u, l + 1); } } }; bool is_equal(vector, int>>& x, vector, int>>& y) { if(x.size() != y.size()) return false; for(int i = 0, n = x.size(); i < n; ++i) { if(x[i].first != y[i].first) return false; } return true; } bool isomorphic(int n, tree& t1, int r1, tree& t2, int r2) { t1.dfs(r1, 0, 0), t2.dfs(r2, 0, 0); if(t1.lvl != t2.lvl) return false; vector l1, l2; vector, int>> s1, s2; vector aux1[n + 1], aux2[n + 1]; for(int i = t1.lvl; ; --i) { if(i == t1.lvl) { //basis: last level; for(auto& u: t1.level[i]) { t1.label[u] = 1; l1.emplace_back(u); } for(auto& u: t2.level[i]) { t2.label[u] = 1; l2.emplace_back(u); } continue; } //push from the last level to this level: for(int& u: l1) { aux1[t1.parent[u]].emplace_back(t1.label[u]); } for(int& u: l2) { aux2[t2.parent[u]].emplace_back(t2.label[u]); } l1.clear(), l2.clear(); //merge all aux-tuples of this level: for(auto& u: t1.level[i]) { sort(span(aux1[u])); s1.emplace_back(aux1[u], u); l1.emplace_back(u); } for(auto& u: t2.level[i]) { sort(span(aux2[u])); s2.emplace_back(aux2[u], u); l2.emplace_back(u); } sort(span(s1)), sort(span(s2)); if(!is_equal(s1, s2)) return false; //label the nodes of this level: t1.label[s1[0].second] = t2.label[s2[0].second] = 1; for(int j = 1, k = s1.size(), idx = 1; j < k; ++j) { if(s1[j].first == s1[j — 1].first) { t1.label[s1[j].second] = t2.label[s2[j].second] = idx; } else { t1.label[s1[j].second] = t2.label[s2[j].second] = ++idx; } } s1.clear(), s2.clear(); } return true; } void hike() { int n; cin >> n; tree t1(n), t2(n); for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; t1.insert(u, v); } for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; t2.insert(u, v); } if(isomorphic(n, t1, 1, t2, 1)) cout << "YES\n"; else cout << "NO\n"; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; cin >> t; while(t--) hike(); return 0; } //farewell, until we meet again..  2. Hashing-based implementation //author: hitch_hiker42; #include using namespace std; //solution: #define int int64_t #define span(a) begin(a), end(a) mt19937_64 mersenne{static_cast(time(nullptr))}; constexpr int mxn = 1e5 + 1, x = 988'244'353, mod = 1e9 + 7; vector adj[2][mxn]; int n, node[2][mxn]; int rng(int l, int r) { return uniform_int_distribution(l, r)(mersenne); } void reset() { for(int i = 1; i <= n; ++i) adj[0][i].clear(), adj[1][i].clear(); } int nodehash(int u, int p, int l, int t, int key) { int hash = l; vector childhashes; for(auto& v: adj[t][u]) if(v != p) { childhashes.push_back(node[t][v]); } sort(span(childhashes)); for(int i = 0, m = childhashes.size(), power = 1; i < m; ++i, (power *= x) %= mod) { (hash += power * childhashes[i] % mod * key % mod) %= mod; } return hash; } void dfs(int u, int p, int l, int t, int key) { for(auto& v: adj[t][u]) if(v != p) { dfs(v, u, l + 1, t, key); } node[t][u] = nodehash(u, p, l, t, key); } void hike() { cin >> n; for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; adj[0][u].emplace_back(v); adj[0][v].emplace_back(u); } for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; adj[1][u].emplace_back(v); adj[1][v].emplace_back(u); } for(int i = 0; i < 5; ++i) { int key = rng(1, x); dfs(1, 0, 0, 0, key); dfs(1, 0, 0, 1, key); if(node[0][1] != node[1][1]) return void(cout << "NO\n"); } if(node[0][1] == node[1][1]) cout << "YES\n"; else cout << "NO\n"; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; cin >> t; while(t--) hike(), reset(); return 0; } //farewell, until we meet again..