help in understanding centroid decomposition!

general
,
1

i have read this tutorial : https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree

I didn’t understand the part : "Hence, we decompose the given tree into O(NlogN) different paths (from each centroid to all the vertices in the corresponding part) such that any path is a concatenation of two different paths from this set. (This is the most important/new/extra part in this DS that should be focused on) "

Which NlogN paths? And if possible please explain how we decompose the path from (4 -> 7) in the example tree there!

2

Suppose you are in level i, in that level each node is a centroid in it’s respective subtree. There is a path from a single node of that level to each and every other ode in it’s own subtree. So overall in a level there are N paths(Because you add up all the paths from that node to some other node). And there are logN levels in all, so the total number paths whose information you will need to store is NlogN.

3

how can this be shown that any path between (u, v) in original tree can be made through two paths (u->c, c->v)?

4

Let u and v be some arbitrary nodes. Let c be their LCA in the centroid tree. This means that c was the centroid and was in the same subtree as u and v sometime but after it was removed, u and v fell into different subtrees. This is why there must be a path from u to c and from c to v.