Comments
+25

a0666 <3 (Look at her IPC problems on CodeChef)
On repeating → Centeroid decomposition, 9 years ago
+29

The most famous application of this technique is for the following types of problems:

  • Compute number of paths in a tree T satisfying some property P
  • Compute the path in a tree T which has highest/lowest some property P

Essentially, you're fixing a vertex v and looking at all paths going through v and then removing it from the tree and recursing on the forest formed. It just happens that the centroid is the best choice of v.

An extended idea of the technique can be used to solve some query based problems, all of which exploit the fact that the "centroid tree" formed after the decomposition has height . For example, you can answer queries of the form .

Check out this blog to learn more.
0

Thanks for your response!

It seems that there is no nice and clean way to solve this problem.
On Barichek → Codeforces Round #407, 9 years ago
+144

All of you are wrong.
0

Could you elaborate some more on your approach?
0

Thank you for your response.

Yes, I figured out how to solve it for that as well. I couldn't quite extend it to sums of squares though and was wondering if there's a nicer solution altogether.