temp_ac's blog

By temp_ac, history, 18 months ago, In English

A rooted binary tree of N ( 1<=N<=1000000 ) nodes is given. You need to answer Q ( 1<=Q<=100000 ) queries.

Each q query contains two inputs : u val

In each query, You need to check whether a node of value val is present in the subtree of node u or not.

I know only a naive approach ( first creating an adjacency list using set STL for each node by finding the subtree of it and then check whether value val is present in the subtree of node u or not ) to this problem. And it is obvious that the solution doesn't fit for given N range.

Can anyone suggest a better approach to this problem ?

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
18 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You can use:

1) Taking queries in a vertexes

2) Create segment tree on a empty array

3) Going on a Euler bypass of a graph and if you are in a new vertex value[vertex]++, when you exit from a vertex value[vertex]--

4) If query is v and val, answer is value[val]

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are you sure about this solution ?

  • »
    »
    18 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Not sure, what is value ? and how does this helps.

    This should work. Flat the tree as described above with euler tour. Now, store the occurrences in some Vector. For each query u val. Find the lower_bound on occurrences wrt l. if this is less than r , then ans is yes else no. L and R are subtree range found by euler tour.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I am answering it very late i know but if someone is facing the issue in this problem in near future they can refer to this