Ahmed_Morsy's blog

heavy light decomposition

By Ahmed_Morsy, 10 years ago, In English

I tried to solve problem e in round 199 xenia and tree using heavy light decomposition but I couldn't figure out the whole idea anyone ?

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

»
10 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

EDIT: Wrong idea. As Xellos said: every problem has a simple, clear, obviously incorrect solution :D

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem can be solve easier with centroid decomposition.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    what is that "centroid decomposition" ?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Centroid of a tree is a vertex that after deleting it, every component will have at most n/2 vertices. You can easily prove its existence. So, using this, you can use divide and conquer on trees and if your time complexity for each merge(conquer) is O(f(n)), then the total complexity would be ; Because you did it at most times on each vertex(every time, the size of the component a vertex u is in it would be half of the previous one).

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Almost give up, but it works. Handle the segment carefully and not affect other segment values (by limit range update between chain root and chain tail of each chain) https://mirror.codeforces.com/contest/342/submission/111296661

→ Reply