Doubt on Centroid Decomposition !

Правка en2, от arjitkansal, 2018-09-05 22:51:02

This doubt is related to the problem :-

Xenia and Tree

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.

Теги centroid decomposition

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский arjitkansal 2018-09-05 22:51:02 266
en1 Английский arjitkansal 2018-09-05 22:48:29 777 Initial revision (published)