This doubt is related to the problem :-
Centroid Decomposition Approach.
This is the link to my solution.
What I did to calculate distances of each node to its parent in centroid tree was while making the Centroid tree, I was storing the distances of current node in the DFS with the previous centroid in the Centroid Tree in a map.
And after the DFS, if distances of some nodes to it's indirect parents are left, I updated them by the formula
dis[current_node][parent of indirect parent]=dis[current_node][indirect parent]+dis[indirect parent][parent of indirect parent];
But I'm getting a WA at test case 12.
Can someone please help me debug this approach ?
I'm sure there is no implementation problem with centroid tree transformation as I used the same code in another problem, there it worked. Only issue can be there in calculation of the distances.
Auto comment: topic has been updated by arjitkansal (previous revision, new revision, compare).
the Logic you are using to find Distance is Wrong. After forming the Centroid tree, the distance doesn't follow the linear distance sum relation over the centroid tree nodes. It is only valid in the original tree. Hence for Distance, you may use the general technique involving LCA to respond distance query in O(logn)