issahaddar5's blog

Distance Between Nodes in A General Tree
By issahaddar5, history, 9 years ago, In English

I am trying to solve this. The graph is a tree, so I represented it as disjoint sets. To find the distance between two nodes I am finding the first common ancestor and adding the distances to reach this ancestor form the starting node and the target node. this is my code and unfortunately its giving wrong answer upon submission.

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

Comments Comments (6)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This is an unrooted tree. Which means you don't know Fr is the parent or To is.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So how to solve the question ? I don't think we can use floyd's algorithm since the constraints are too big.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 9   Vote: I like it +1 Vote: I do not like it

      This can be solved by first change the unrooted tree to a rooted tree by simlpy pick a random node (like node 1) as the root. Then in each query just find the lowest common ancestor (lca) of two nodes in O(log n) by using sparse table or segment tree. The distance between two nodes are (depth(Fr)-depth(lca))+(depth(To)-depth(lca)).

      You can have the information of finding lca in this blog http://codeforces.com/blog/entry/16221

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

.

→ Reply
»
3 years ago, # |
  Vote: I like it -25 Vote: I do not like it

D.collision This is a similar problem. Give it a try!!

→ Reply