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

Great job :D Thank you :)

Here's a nice problem about Centroid Decomposition : Race (although it's from IOI '11 not codeforces)

Can't it be solved without CD?

It can be solved using DSU on Tree.

The complexity is always O(nlogn) ?

So it doesn't depend on the problem or on the requested queries ?

Lol, don't try to memorize it. Understand why it is

O(N*logN). You build the centroid-decomposition-tree. The tree haslogNlevels. From each level, you do a DFS and visit atmostNnodes in total. So, you performNlogNoperations. 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 anotherlogNfactor. 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).Thanks a lot :D

Your reply here helps me a lot after 3 years.

Mahmoud and a xor trip usually fails with cd due to the tight time limit. O(nlognlogM) is sadly too much.

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.)

I ain't gonna solve it using cd :D

I'm just warning since I've seen many cd-oriented solutions failing with TLE here.

if you want you can add these problems :

150E — Freezing with Style

293E — Close Vertices

Done

Thanks :D

your welcome

How is 183C - Cyclic Coloring related to centroid decomposition?

you are right :) sorry. repeating pls remove Cyclic Coloring

Auto comment: topic has been updated by repeating (previous revision, new revision, compare).348E - Pilgrims

why just problems on CF ?

Because this blog's on CF !!

that doesn't make sense!

uva 12772

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=823&page=show_problem&problem=4625

I only came up with O(n*sqrt(n)*lg(n)) complexity, which will get tle...

Tree2 from Timus can be solved using multiple techniques and Centroid Decomposition is one of them

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?

thanks :)

Can anyone help me with Centroid Decomposition approach to the problem 161D("Distance in Tree")(http://codeforces.com/contest/161/problem/D)

CD is so overkill. Subtree DP is faster and easier.

with subtree DP you achieve an NK solution?

18045256

Thanks

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 :)

Subtree DP? Isn't that just the most basic DP on tree? I think I must have missed something.

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.

Can you explain the "awesome technique"? Thanks!

If you want to read about "DP on Tree" here's a tutorial:

https://codeforces.com/blog/entry/20935

I haven't read all of it but it looks promising.

http://codeforces.com/contest/161/submission/31966570

Should be self explanatory i think.

http://codeforces.com/contest/161/submission/31470816 This is also the effecient way

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

It's OK

Thanks for your help

New problem with CD: http://codeforces.com/contest/914/problem/E

Can someone explain the solution of 766E — Mahmoud and a xor trip with Centroid Decomposition? Thanks in advance!

No.

Stop downvoting!!

Can anyone tell the centroid decomposition solution to 161D? I did it using a n*k dp.

see rumblefool solution.. he solved it using cd

766E , centroid decomposition is not fast enough..

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/32760352

Here'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.

yeah, I 'll try to improve my code base on your code.

Thanks for share~

old one: https://codeforces.com/contest/766/submission/51847865

new one: https://codeforces.com/contest/766/submission/54057910

There was a flaw in my answer's rekoning part, which cause square time complex~.

Now it's fixed and fast enough.

1156D - 0-1-Tree also can be solved using Centroid Decomposition.

SpoilerHere is my solution using CD: 54143834

cd is an overkill for this problem

A recent problem of CF 563 Div2 : F. Ehab and the Big Finale

khung

This is a nice one: https://codeforces.com/contest/914/problem/E

https://codeforces.com/problemset/gymProblem/100633/D?locale=ru

Interactive Question

Two from codechef:

https://www.codechef.com/MARCH21A/problems/RWALKS

https://www.codechef.com/COOK132A/problems/MAXJMP