Hello All,
I was recently trying to solve this problem: https://codeforces.net/problemset/problem/1210/C. After realizing it was finding the sum of gcd on paths, I thought that this problem was a direct application of Centroid Decomposition.
However, my submission (https://codeforces.net/contest/1210/submission/61229151) got WA on test case 6. I do not think my code is the problem as I have verified it with this problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=286
I am wondering if my logic of choosing to use centroid decomposition is wrong. Any help would be greatly appreciated!
I don't think that we need centroid decomposition here, since the tree is always rooted at node $$$1$$$, we only need to calculate the value for nodes that belong in the subtree of every node. I'm not sure how to exactly solve the problem but one thing that may come in handy is that when solving this on array one big tree that is chain (1 — 2 — 3 — ... — n) for each node comparing to his parents there are $$$O( \log N)$$$ different values for the gcd result.
Using the fact that centroid decomposition can be performed on your tree isn’t “right” or “wrong.” It might not be helpful in solving the problem, but if you apply it correctly you will still get the right answer.
The original problem here asks for the sum of a function over all vertical paths in a rooted tree. You aren’t computing the same thing when you find paths going down from your centroids.