Farthest node(b) from a node (a) in a tree
Difference between en1 and en2, changed 30 character(s)
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)↵


History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English dragonzurfer 2017-06-17 09:19:52 30
en1 English dragonzurfer 2017-06-17 09:18:59 888 Initial revision (published)