karanmishra8997's blog

Union Of Two Trees
By karanmishra8997, history, 6 years ago, In English

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?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

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

    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?

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

      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.

      → Reply