Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя thegodfather

Автор thegodfather, история, 8 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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)