Tobby_And_Friends's blog

Centroid Decomposition related problems
By Tobby_And_Friends, history, 7 years ago, In English

I just learned centroid decomposition today. Please refer me some problems on Centroid Decomposition. I read the topic from this link: https://tanujkhattar.wordpress.com/2016/01/10/centroid-decomposition-of-a-tree/ so please provide me some additional problems to begin with.

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

Comments Comments (9)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

321C - Командир Ciel

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

Nov16 Kirito and Memeland
766E. Although the official solution is using DP but we can also solve it using Centroid decomposition with O(nlog2n) complexity.

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

716E - Цифровое дерево

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

Simple problem 161D - Расстояние в дереве
Hard problem (but centroid decomposition is a simple part of solution): 776F - Пари Шерлока и Мориарти

Also a good problem from acm.timus.ru — link

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

    How did you use centroid decomposition on 161D?

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

      Lets fix centroid C of current tree, so we can find all pathes with length k thats passes throw C. How to do it: fix the order of subtrees of C and process it one by one, we should store map with pairs <dist from C, count>, and when we process subtree for each vertex with dist X from C we should add map[K-X] to answer, after subtree will be processed, we should update the map. Hope it helps.

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

IOI 2011 Race
COI 2017 Problem D

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

This is pretty difficult https://csacademy.com/contest/archive/task/flareon

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

Refer this blog post: Centroid Decomposition

→ Reply