I recently came across a problem called [GERALD](https://www.codechef.com/problems/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:↵
↵
<node>,(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)↵
↵
↵
↵
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:↵
↵
<node>,(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)↵
↵
↵
