### repeating's blog

By repeating, history, 5 years ago,

Hi

These are some problems about Centroid Decomposition , you can learn this algorithm here .

Its complexity is O(nlogn)

I hope these problems would be useful for you :)

If there are another problems on CF please put it on comment !!

UPD : The list has been updated

• +89

 » 5 years ago, # |   +14 Great job :D Thank you :)
 » 5 years ago, # |   +17 Here's a nice problem about Centroid Decomposition : Race (although it's from IOI '11 not codeforces)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Can't it be solved without CD?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 It can be solved using DSU on Tree.
 » 5 years ago, # |   -7 The complexity is always O(nlogn) ? So it doesn't depend on the problem or on the requested queries ?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +21 Lol, don't try to memorize it. Understand why it is O(N*logN). You build the centroid-decomposition-tree. The tree has logN levels. From each level, you do a DFS and visit atmost N nodes in total. So, you perform NlogN operations. If you do other stuff while visiting the nodes, the complexity will change too. For example, if after visiting each node, you insert into some global set, you introduce another logN factor. So, yes, it depends on the problem and the requested queries. O(NlogN) is just the bound on the total number of nodes you visit during the DFSs (a particular node may be visited multiple times from different centroids).
•  » » » 5 years ago, # ^ |   0 Thanks a lot :D
•  » » » 16 months ago, # ^ |   +8 Your reply here helps me a lot after 3 years.
 » 5 years ago, # |   0 Mahmoud and a xor trip usually fails with cd due to the tight time limit. O(nlognlogM) is sadly too much.
•  » » 5 years ago, # ^ |   +3 I don't understand why you'd solve 766E - Mahmoud and a xor trip using CD anyway. In problems where simple dynamic programming suffices, there's no need to go through the hassle of implementing centroid decomposiotion. Reserve it for problems where all paths rooted at some vertex can't be represented by 2 integers total.(I guess practicing CD is a reason enough. Still, I'd explore simpler solutions.)
•  » » » 5 years ago, # ^ |   +3 I ain't gonna solve it using cd :DI'm just warning since I've seen many cd-oriented solutions failing with TLE here.
 » 5 years ago, # | ← Rev. 3 →   +14 if you want you can add these problems :150E — Freezing with Style293E — Close Vertices
•  » » 5 years ago, # ^ |   +3 Done Thanks :D
•  » » » 5 years ago, # ^ |   +3 your welcome
•  » » 5 years ago, # ^ |   +13 How is 183C - Cyclic Coloring related to centroid decomposition?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +11 you are right :) sorry. repeating pls remove Cyclic Coloring
 » 5 years ago, # |   +8 Auto comment: topic has been updated by repeating (previous revision, new revision, compare).
 » 5 years ago, # |   +10
 » 5 years ago, # |   -10 why just problems on CF ?
•  » » 5 years ago, # ^ |   0 Because this blog's on CF !!
•  » » » 5 years ago, # ^ |   0 that doesn't make sense!
 » 5 years ago, # |   0 uva 12772https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=823&page=show_problem&problem=4625I only came up with O(n*sqrt(n)*lg(n)) complexity, which will get tle...
 » 5 years ago, # |   +1 Tree2 from Timus can be solved using multiple techniques and Centroid Decomposition is one of them
•  » » 5 years ago, # ^ |   +1 Can you elaborate on your approach? I solved it using CD, however my solution is a bit slow(0.3 seconds, there are submissions in less than 0.1)? What is your complexity?
 » 5 years ago, # |   0 thanks :)
 » 5 years ago, # | ← Rev. 2 →   0 Can anyone help me with Centroid Decomposition approach to the problem 161D("Distance in Tree")(http://codeforces.com/contest/161/problem/D)
•  » » 5 years ago, # ^ |   0 CD is so overkill. Subtree DP is faster and easier.
•  » » » 5 years ago, # ^ |   0 with subtree DP you achieve an NK solution?
•  » » » » 5 years ago, # ^ |   0
•  » » » » » 5 years ago, # ^ |   0 Thanks
•  » » » 4 years ago, # ^ |   0 Sorry, may I ask if it is an official name? It is an awesome technique. I have seen it in USACO once but never thought that it would be applicable here :)
•  » » » » 4 years ago, # ^ |   0 Subtree DP? Isn't that just the most basic DP on tree? I think I must have missed something.
•  » » » » » 4 years ago, # ^ |   0 Well, it is not like there exists an internationally standardized curriculum about DP in this world :v , all I know about what-so-called "DP on tree" is that the technique is DP and the problem involves tree.
•  » » » » » » 4 years ago, # ^ |   0 Can you explain the "awesome technique"? Thanks!
•  » » » » 3 years ago, # ^ |   0 If you want to read about "DP on Tree" here's a tutorial:https://codeforces.com/blog/entry/20935I haven't read all of it but it looks promising.
•  » » 4 years ago, # ^ |   0 Should be self explanatory i think.
•  » » 4 years ago, # ^ |   0 http://codeforces.com/contest/161/submission/31470816 This is also the effecient way
 » 5 years ago, # |   +8 Don't get angry if I mention this problem even if it's not on CF: I think is very interesting Centroid Decomposition problem, and it's pretty difficult. https://csacademy.com/contest/archive/task/flareon
•  » » 5 years ago, # ^ |   0 It's OK Thanks for your help
 » 4 years ago, # |   +8 New problem with CD: http://codeforces.com/contest/914/problem/E
 » 4 years ago, # |   +6 Can someone explain the solution of 766E — Mahmoud and a xor trip with Centroid Decomposition? Thanks in advance!
•  » » 4 years ago, # ^ |   -37 No.
•  » » » 4 years ago, # ^ |   +14 Stop downvoting!!
 » 3 years ago, # |   0 Can anyone tell the centroid decomposition solution to 161D? I did it using a n*k dp.
•  » » 3 years ago, # ^ |   +3 see rumblefool solution.. he solved it using cd
 » 3 years ago, # |   -9 766E , centroid decomposition is not fast enough..
•  » » 3 years ago, # ^ |   +5 While it might be easier to solve with DP instead of CD (Centroid Decomposition), it still can be done with CD pretty comfortably I think. https://codeforces.com/contest/766/submission/32760352Here's my solution for example using CD that takes less than 600ms where TL is 2s. I am not saying that using CD here is a better idea, just showing that it's possible to do it with CD.
•  » » » 3 years ago, # ^ |   +3 yeah, I 'll try to improve my code base on your code.Thanks for share~
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +8 There was a flaw in my answer's rekoning part, which cause square time complex~.Now it's fixed and fast enough.
 » 3 years ago, # |   0 1156D - 0-1-Tree also can be solved using Centroid Decomposition. SpoilerHere is my solution using CD: 54143834
•  » » 3 years ago, # ^ |   0 cd is an overkill for this problem
 » 3 years ago, # |   +5 A recent problem of CF 563 Div2 : F. Ehab and the Big Finale
•  » » 21 month(s) ago, # ^ |   0 khung
 » 2 years ago, # |   0 This is a nice one: https://codeforces.com/contest/914/problem/E
 » 21 month(s) ago, # |   0
 » 17 months ago, # |   0
 » 5 months ago, # |   0