### dragonzurfer's blog

By dragonzurfer, history, 19 months ago, ,

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)

 » 19 months ago, # |   +3 Auto comment: topic has been updated by dragonzurfer (previous revision, new revision, compare).
 » 19 months ago, # |   +8 The problem is invisible right now, but I think it can be solved by simple DFS to calc the farthest node from each node, so dist[i] will contains the distance to the farthest node from node iwhen you consider the farthest node from node u, it could be found in the subtree of node u or outside, to calculate the farthest node from node u in its subtree is trivial, but outside is a little bit confusing, to calculate this value, for each node keep a vector vec[u] contains the farthest distance node in the subtree of node v where v is a direct child of u, then when you do DFS, you can pass a parameter called MaxUp that holds the farthest node from outside subtree of node u, this can be done fast by calculating prefix and suffix max on vector vec.
 » 19 months ago, # | ← Rev. 3 →   +8 Farthest node from any vertex of tree is actually one of ends of its diameter, which you can compute using two dfses, and then compute distances to vertices from ends using another two dfses.
•  » » 13 months ago, # ^ |   -8 What is the proof?
•  » » 7 months ago, # ^ |   -16 what if there are many diameters of same length!
•  » » » 7 months ago, # ^ |   +3 Doesn't matter. The longest path is (path from u to center) + (path from center to other end of some diameter).
•  » » » » 7 months ago, # ^ |   0 what is center?
•  » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 There is a nice article about tree centroids here. They're also usefull when you need to find if two trees are isomorphic.
•  » » » » » » 7 months ago, # ^ | ← Rev. 2 →   +7 Center: vertex in a tree through which every longest path goes through.Centroid: vertex in a tree that when you take it as root, the subtrees have size <= floor(n / 2) where n is the size of the tree.They are different.
•  » » » » » » » 7 months ago, # ^ |   0 thanks man :)
 » 19 months ago, # |   +2 Farthest node from any node can be calculated using simple BFS .
•  » » 13 months ago, # ^ |   -8 how?
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 Mhammad1 has explained above .
•  » » » » 13 months ago, # ^ |   0 it's called DFS
•  » » 7 months ago, # ^ |   -24 BFS can calculate the nearest node not the farthest.
•  » » » 7 months ago, # ^ | ← Rev. 3 →   +5 It's a tree, there is only one path between two nodes. So, you can — for sure — use a BFS (or a DFS) to get the farthest node and it's, actually, the most effective way (if there is only a single query per graph).
•  » » » » 7 months ago, # ^ |   -19 if is it tree ,yeah it is true .