Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

radhey_maa's blog

Centroid Decompostition in QTREE
By radhey_maa, history, 9 years ago, In English

Can QTREE be solved using centroid decomposition. I solved QTREE5 using the method, but I am struggling to solve QTREE using the method. Problem

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I see two solution ideas: 1) HLD + segment tree. 2) Link-Cut Tree (almost no extra code)

I don't think centroid decomposition is a good approach here due to the updates required. Although there may be a solution using centroid decomposition trees but that solution doesn't seem as obvious to me.

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

    Thanks, but I just wanted to practice the technique. I don't know if this means that all QTREEs can be solved using centroid decomposition or it just involves distances on trees.

    → Reply