Блог пользователя issahaddar5

Distance Between Nodes in A General Tree
Автор issahaddar5, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 9   Проголосовать: нравится +1 Проголосовать: не нравится

      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

      → Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится -23 Проголосовать: не нравится

.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

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

→ Ответить