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