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.
321C - Командир Ciel
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.
716E - Цифровое дерево
Simple problem 161D - Расстояние в дереве
Hard problem (but centroid decomposition is a simple part of solution): 776F - Пари Шерлока и Мориарти
Also a good problem from acm.timus.ru — link
How did you use centroid decomposition on 161D?
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.
IOI 2011 Race
COI 2017 Problem D
This is pretty difficult https://csacademy.com/contest/archive/task/flareon
Refer this blog post: Centroid Decomposition