ADA and Orange Tree SPOJ (LCA)
Difference between en2 and en3, changed 49 character(s)
I tried solving the problem the following way:↵
1) Using dfs I maintained the euler tour of the graph,height(or depth) of nodes,along with first and last occurence of index in ↵
   euler tour.↵
2) Built a segment tree to give the minimum depth node in an interval along with its index.↵
3) Built another segment tree to give the number of different colors within an interval in the euler tour array.(I used Bitsets ↵
   in java here).↵
4) for each query I calculate first the lca of the given nodes, call it X,using first segment tree.↵
5) then using first and last pos of X in the euler tour I calculate the number of different colors in this interval,using second ↵
   segment tree.↵

But unfortunately I have been getting TLE at 15th test case. I tried optimising it a lot but its not working. Any help would be appreciated!↵


UPDATE: Instead of using segment tree to find the number of different color,instead for each node I calculated the number of different colors in a subtree using BitSet while dfs itself only. Now I'm calculating only the lca in log(n) time while answering ↵
the number of different colors in a subtree in O(1). But guess what? Now I'm getting NZEC on the same test case 15 which I don't get why:(. Any help would be appreciated:)


UPDATE: GOT accepted with c++ the same logic!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English SLIMSHADYNICK 2020-03-14 22:17:13 49 Tiny change: 'reciated:)' -> 'reciated:)\n\nUPDATE: GOT accepted with c++ the same logic!'
en2 English SLIMSHADYNICK 2020-03-14 03:53:53 432
en1 English SLIMSHADYNICK 2020-03-13 22:19:21 860 Initial revision (published)