A problem with path queries and path updates

Revision en1, by MODDI, 2023-02-19 23:15:26

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English MODDI 2023-02-19 23:38:04 2 Tiny change: ' node has A number A(' -> ' node has a number A(' (published)
en2 English MODDI 2023-02-19 23:16:35 26
en1 English MODDI 2023-02-19 23:15:26 759 Initial revision (saved to drafts)