thegodfather's blog

A query about centroid decomposition
By thegodfather, history, 7 years ago, In English

Reference blog :- https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree

Once we have centroid decomposition of a tree we claim that a path between two nodes x and y can be decomposed into two paths- x to (x,y)'s LCA and y to the LCA. But in the centroid tree the path is not the same path as it was not in the original tree, as some new edges are formed and old edges are removed as part of the centroid tree construction. So, while solving problems using this tree how is it like that this fact of having some new edges and some old edges removed does not matter?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

You just use this fact about path decomposition, but distance from two vertices you use from real tree, not centroid.

for example, to find a distance to two vertices, you get lca in centroid tree and then use real distance from x to lca, and from y to lca (you can precalc it while building centroid tree)

→ Reply