_idgaf_'s blog

By _idgaf_, history, 3 years ago, In English

Given a tree with N nodes, each node has some value assigned to it. The tree is rooted at node 1 (1-based indexing). For each node, find number of ancestors with value greater than current node. 1<=N<=70000 0<=Value of node<=1e9

eg: N=5 value = [5,4,3,2,1] (remember 1 based indexing) edges = [[1,2],[2,3],[3,4],[4,5]]

Output: [0,1,2,3,4]

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

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Just do a dfs and maintain ordered set till a particular node from the root. So, whenever you enter a node add its value to the ordered set and whenever you exit it remove that value from the ordered set. Now, because its an ordered set you can easily answer your query. For implementing ordered set you can use pbds or treap.

Also, you can compress the values and use segment tree for updating the values and for answering query use range sum.