A query about centroid decomposition

Правка en1, от 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский thegodfather 2017-02-24 06:28:41 615 Initial revision (published)