yyyvvvyyy's blog

Alternative solution to standard tree query problem?
By yyyvvvyyy, history, 7 years ago, In English

I was solving this problem which seemed like a pretty much standard problem of persistent segment tree but i came across this solution which seems to use some dfs ordering of nodes and i'm unable to figure out what is going on?

Problem: Given a tree (100000 nodes) and a value in each node, and for each query you are given 2 nodes and a value V , you have to find number of nodes whose value is less than V.

solution: https://www.hackerearth.com/challenge/college/programmers-parliament/algorithm/freaky-frequencies/submission/7492012/

This is my first time on codeforces. Thanks in advance

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

Comments Comments (3)
| Write comment?
»
7 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it 
You can solve it this way - 
1. You need to notice that we need a data structure to answer queries of the form - How many prime numbers between L and R exist from node to some_ancestor(node). This value is equal to the number of prime nos. between L and R from root to node - number of prime nos. between L and R from root to some_ancestor(node). The obvious choice may be segment tree/fenwick tree. I will explain the soln. using segment tree.
2. For each query, compute LCA(A,B)=lca. This lca is the ancestor of both A and B, and we are interested in it. 
3. We will be processing the queries offline. To do this, for each query, find LCA(A,B)=lca and for each such lca, store in memory the answer - How many prime nos. between L and R exist from root to lca for only those L,R values in queries in which LCA(A,B) = lca. You can do this using a single DFS from root and upto each node in DFS, maintain a segment tree storing all the values from the root upto that point. 
Each node of this segment tree will represent the number of prime nos. which were seen on the path from the root to that node in range [left,right]. When you are on a particular node, you answer the queries for all L,R for which this node becomes the lca.
4. Do another DFS from root using the same method as in step - 3 (using another segment tree), but this time, you compute the answer described in step - 1.
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We basically divide the query range from u to v as root to u, root to v and root to lca(u,v). Compute the answer for these paths, and you can restore the answer for the original query. To compute the answer for a particular node, we first store all the ranges (l,r) for that particular node. Notice that if all the values from the root to a node v are added to a bit, then we can find the answer using one range query. Now we can just perform dfs, add a node to the bit at the beginning of the DFS call and remove it from the BIT at the end of the DFS call. This will ensure that when we are a node, all its ancestors are in the bit.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Edit : same as above

→ Reply