Why does Centroid Decomposition get WA on this problem?

Revision en1, by wet_water, 2019-09-25 02:42:56

Hello All,

I was recently trying to solve this problem: https://mirror.codeforces.com/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://mirror.codeforces.com/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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English wet_water 2019-09-25 02:43:31 2 Tiny change: '/index.php page=viewp' -> '/index.php?page=viewp'
en1 English wet_water 2019-09-25 02:42:56 669 Initial revision (published)