Need help in a segment tree problem

Revision en4, by Lakh, 2018-05-29 08:37:23

I am trying to solve https://www.hackerrank.com/contests/world-codesprint-13/challenges/landslide.

Here given a tree of N(N<=2*10^5) nodes and Q (Q<=2*10^5) queries of 3 types:

1. d x y -- Remove the edge between city x and y if it exists else ignore this query.
2. c x y -- Add the edge between city x and y if previously an edge was present between x and y else ignore this query.
3. q x y -- Find the distance between x and y if there exists a path between x and y else print "impossible".
My approach:

I first performed dfs to store the in[] and out[] time of each node and code for finding LCA of two nodes. Now I created a segment tree on the basis of the in[] array and initialized each node to value 1 meaning that all nodes are initially form a single connected component. I took a variable counter=2. 

Now for query of first type , suppose x is parent of y then I just updated all nodes in subtree of y to value counter using lazy propagation such that it represents a different component and increment counter by 1.

For query of 2nd type, if x was parent of y previously, then I just updated the entire subtree of y to the current value in node x so that entire subtree of y is again attached to subtree of x and y becomes part of the component to which x belongs.

For query of 3rd type I first computed LCA of x and y then determined the current values of node x, node y and node[LCA(x,y)]. If all the three values are not same then this means that x and y are not connected else i just print the distance between the nodes x and y as dis[x]+dis[y]-2*dis[LCA(x,y)]

Some of the tescases are failing. I am not able to understand what is wrong with my approach. Please suggest the problem with this approach.

My code: https://ideone.com/cXf4NX

Tags tree, lca, dfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Lakh 2018-05-29 08:37:23 29
en3 English Lakh 2018-05-29 08:02:43 99
en2 English Lakh 2018-05-29 07:58:09 38 Tiny change: 'roach.\n\n\n' -> 'roach.\n\nMy code: https://ideone.com/cXf4NX\n\n\n'
en1 English Lakh 2018-05-29 07:55:13 1756 Initial revision (published)