dragonzurfer's blog

Farthest node(b) from a node (a) in a tree
By dragonzurfer, history, 7 years ago, In English

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)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by dragonzurfer (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply