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)