Fake Plastic Trees

Forget the scary operation definition for a second. The whole problem collapses into a very small DP once you look at it the right way.

The key abstraction

For each node $v$, we only care about two things about its subtree:

• the minimum number of operations needed to make the whole subtree valid;
• with that minimum number of operations, how much this subtree can still contribute upward to $v$'s parent.

Let's define:

• $ops_v$ = minimum operations needed for the subtree of $v$;
• $mx_v$ = the largest integer such that, using exactly $ops_v$ operations, the subtree of $v$ can make its contribution to $p_v$ be any value in $[0, mx_v]$ while keeping every node in the subtree valid.

That second definition is the entire damn trick.

Why children only give an interval

Suppose child $u$ has already been solved, and its subtree can contribute any value in $[0, mx_u]$ to $v$.

Then if $v$ has children $u_1, u_2, \dots, u_k$, together they can contribute any total value in

$[0, S], \qquad S = \sum mx_{u_i}.$

Why? Because each child independently gives an interval $[0, mx_u]$, and the sum of intervals is still an interval. No cursed subset-DP nonsense here.

So after processing all children, node $v$ sees just one number:

$S = \sum_{u \text{ child of } v} mx_u.$

Now what?

Case 1: $S < l_v$

Then even if every child subtree helps as much as possible, node $v$ still cannot reach its lower bound.

So one more operation is unavoidable.

And if we need one extra operation anyway, the best place to start it is at $v$ itself. Starting it deeper is never better: one operation at $v$ can directly make $v$ as large as we want up to $r_v$, which is as good as it gets for helping ancestors too.

So in this case:

$ops_v = \sum ops_u + 1, \qquad mx_v = r_v.$

Why $mx_v = r_v$? Because with one operation at $v$, we can keep the subtree valid and make the contribution to the parent be any value from $0$ to $r_v$.

Case 2: $S \ge l_v$

Then we do not need a new operation at $v$.

The children can already make $v$ large enough.

The only thing that limits how useful this subtree is to the parent is the upper bound of $v$ itself. So the maximum upward contribution is

$mx_v = \min(S, r_v).$

And the operation count stays

$ops_v = \sum ops_u.$

Why is that enough? Because the children can make $v$ receive any amount up to $S$, and once $v$ receives some value $y$, the operations can be tuned so that the parent gets any value $x \le y$. So every value in $[0, \min(S,r_v)]$ is achievable upward.

The recurrence

So the entire DP is:

$S = \sum_{u \text{ child of } v} mx_u$

$$mx_v = \begin{cases} r_v, & S < l_v,\\ \min(S, r_v), & S \ge l_v. \end{cases}$$

And every time $S < l_v$, we add $1$ to the answer.

That's it. Seriously. The operation definition looks like it wants a PhD thesis; the solution is just a greedy postorder DP.

Why reverse order works

The input guarantees $p_i < i$. So every parent has a smaller index than its children.

That means processing nodes in order

$n, n-1, \dots, 1$

is already a valid postorder traversal.

So you don't even need DFS recursion. Just accumulate each node's $mx$ into its parent.

Complexity

For each test case, every node is processed once.

• Time: $O(n)$
• Memory: $O(n)$

Across all test cases, that's $O\!\left(\sum n\right)$, which fits easily.

Tiny sanity check

If $v$ is a leaf, then $S=0$. Since $l_v \ge 1$, we always have $S < l_v$, so we must spend one operation there, and $mx_v = r_v$. That matches the recurrence perfectly.

So yeah — bottom-up, sum child capacities, and whenever the sum is too small, smack one operation on the node. Clean, greedy, accepted.