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

Union Of Two Trees
Автор karanmishra8997, история, 6 лет назад, По-английски

Suppose I have n nodes and Q queries are given. Each query can be one of the following types: 1) 1 x y: make edge between point x and y. 2) 2 x y: Find distance between x and y (number of edges in the path from x to y). 3) 3 x: Number of nodes of the component in which node x resides. It is guaranteed that after making edge between x and y, tree structure will be as it is i.e. there will be no query such that it makes a cycle. Constarints: 1 <= N,Q <= 100000 I know that we can join x and y and make an edge by Disjoint Set Union technique. By using that, we can also store number of nodes in each component. But I don't know how to solve query (2). Can anybody help?

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

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Just build the whole tree before answering any query. Upon a query of type 2, check if at that time x and y are in the same component; if they are, calculate the distance between them based on the complete tree.

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

    But how to calculate distance efficiently? If I find distance in every query using dfs or bfs. It will be time limit exceeded. Can you explain with a small example?

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

      You may use LCA (Lowest Common Ancestor) for this. Given two nodes u and v and their lowest common ancestor L, the distance between them is depth[u] + depth[v] - 2·depth[L].

      You can read about LCA here: link.

      → Ответить