dragonzurfer's blog

By dragonzurfer, history, 12 months 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)

 
 
 
 

»
12 months 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).

»
12 months 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.

»
12 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    What is the proof?

  • »
    »
    5 days ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    what if there are many diameters of same length!

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what is center?

        • »
          »
          »
          »
          »
          5 days ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            5 days ago, # ^ |
            Rev. 2   Vote: I like it +7 Vote: I do not like it

            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.

»
12 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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