rpthegreat's blog

Find number of ancestors whose weight is greater than given query and node
By rpthegreat, history, 7 years ago, In English

Hello, Given a tree (nodes and their weight) and query which contains two number node (of tree guaranteed )and value c . I need to find number of ancestors which has weight greater than c. I saved query and sorted according to their query value. I stored graph node and their respective weight in 2-D array and sorted according to their weight. I set bit array initially all zero and start visiting query array from last. Now how to use segment tree for query. Do i need to use another concept ? please help me . Thank you.

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Ok, first what you need to do is represent the tree as array (using in-order). For every vertex you will have from[v] and to[v] (the range in the array that is the subtree of v) .Then put all the vertices and the queries in the same array and sort them in non-increasing way. When you are at a vertex you must make seg[from[v]]+=1 and seg[to[v]+1]-=1 . Now when you are facing a query you must simply output the sum [1,from[v]]

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

First make a list of queries for every node, then do a DFS keeping an order-statistic tree, like a treap or the policy-based data structures from the STL. When you enter a node, you add the value to the tree, when you exit the node you remove the value. To answer a query, just find the order of the first key greater than c in the tree.

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

You can do one dfs keeping all ancestors of current node in an order statistics tree keyed by node weight. Answering queries for current node is just counting number of elements in the order statistics tree with value > c

→ Reply