A query about centroid decomposition

Revision en1, by thegodfather, 2017-02-24 06:28:41

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English thegodfather 2017-02-24 06:28:41 615 Initial revision (published)