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)