Farthest node(b) from a node (a) in a tree

Правка en1, от dragonzurfer, 2017-06-17 09:18:59

I recently came across a problem called GERALD. The problem requires finding the farthest node. The solution given was to solve it using HLD. But I was thinking if there is some other way of doing it. I came across Centroid Decomposition. So I though of decomposing the tree into the levels(l1,l2,l3....lk) in the new centroid graph. Then sort each level in dfs order. Then for a particular node(a) the farthest node(b) would be the first element in the lowest level of the centroid graph. This level should not contain node(a).

example graph: N=10 E=9 EDGE 1:1 2 EDGE 2:1 10 EDGE 3:2 3 EDGE 4:2 4 EDGE 5:4 5 EDGE 6:4 6 EDGE 7:5 7 EDGE 8:7 8 EDGE 9:10 9

CENTROID GRAPH: ,(parent)

level 0 :2(-1) level 1 :10(2) 5(2) 3(2) level 2 :9(10) 7(5) 4(5) 1(10) level 3 :8(7) 6(4)

Теги #trees, centroid decomposition

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский dragonzurfer 2017-06-17 09:19:52 30
en1 Английский dragonzurfer 2017-06-17 09:18:59 888 Initial revision (published)