| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 167 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
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]
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.