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 node i
when 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.
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?
https://codeforces.com/blog/entry/69604?#comment-541142
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 .