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)

Auto comment: topic has been updated by dragonzurfer (previous revision, new revision, compare).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 nodeiwhen you consider the farthest node from node

u, it could be found in the subtree of nodeuor outside, to calculate the farthest node from nodeuin its subtree is trivial, but outside is a little bit confusing, to calculate this value, for each node keep a vectorvec[u] contains the farthest distance node in the subtree of nodevwherevis a direct child ofu, then when you doDFS, you can pass a parameter calledMaxUpthat holds the farthest node from outside subtree of nodeu, this can be done fast by calculating prefix and suffix max on vectorvec.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.

What is the proof?

what if there are many diameters of same length!

Doesn't matter. The longest path is (path from u to center) + (path from center to other end of some diameter).

what is center?

There is a nice article about tree centroids here. They're also usefull when you need to find if two trees are isomorphic.

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.

thanks man :)

Farthest node from any node can be calculated using simple BFS .

how?

Mhammad1 has explained above .

it's called DFS

BFS can calculate the nearest node not the farthest.

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).

if is it tree ,yeah it is true .