I came across this problem while practicing, but I didn't solve it, some suggestions for these types of problems would be appreciated. We have a tree with n nodes(n <= 300000), and each node has a number A(1 <= A <= 10^9). The first line of the input consists of two numbers n and A0 (the number of nodes and the number on node 1). Each of the next n-1 lines has two numbers Ai and the parent of node i. For every node except the root, we need to find the number of nodes that have a strictly smaller number than the current node. Then we need to update every node on the path from the current node to the root, set Aj = max(Aj, Ai)

Example:
5 400
350 0
300 1
450 2
420 0
550 3
Answer:
0
0
3
0
4