CF932D Tree

You are given a node of the tree with index $ 1 $ and with weight $ 0 $ . Let $ cnt $ be the number of nodes in the tree at any instant (initially, $ cnt $ is set to $ 1 $ ). Support $ Q $ queries of following two types: -  Add a new node (index $ cnt+1 $ ) with weight $ W $ and add edge between node $ R $ and this node. -  Output the maximum length of sequence of nodes which 1. starts with $ R $ . 2. Every node in the sequence is an ancestor of its predecessor. 3. Sum of weight of nodes in sequence does not exceed $ X $ . 4. For some nodes $ i,j $ that are consecutive in the sequence if $ i $ is an ancestor of $ j $ then $ w[i]>=w[j] $ and there should not exist a node $ k $ on simple path from $ i $ to $ j $ such that $ w[k]>=w[j] $ The tree is rooted at node $ 1 $ at any instant. Note that the queries are given in a modified way.

N/A

N/A

In the first example, $ last=0 $ \- Query 1: 1 1 1, Node $ 2 $ with weight $ 1 $ is added to node $ 1 $ . \- Query 2: 2 2 0, No sequence of nodes starting at $ 2 $ has weight less than or equal to $ 0 $ . $ last=0 $ \- Query 3: 2 2 1, Answer is $ 1 $ as sequence will be $ {2} $ . $ last=1 $ \- Query 4: 1 2 1, Node $ 3 $ with weight $ 1 $ is added to node $ 2 $ . \- Query 5: 2 3 1, Answer is $ 1 $ as sequence will be $ {3} $ . Node $ 2 $ cannot be added as sum of weights cannot be greater than $ 1 $ . $ last=1 $ \- Query 6: 2 3 3, Answer is $ 2 $ as sequence will be $ {3,2} $ . $ last=2 $