Maximizing Node Deletions on a Load‐Constrained Cherry Blossom Tree

In a magical forest long ago, a group of rabbits decided to visit the cherry blossoms. The cherry blossom tree is a special rooted tree with (n) branching points (nodes) numbered from (0) to (n-1) (node (0) is the root), connected by (n-1) branches. Each node (i) initially carries (c_i) cherry blossoms. Moreover, every node (whether it is kept or not later) has a maximum load limit (m). For any node (i) that remains in the tree, the following condition must hold: [ \text{son}(i) + c_i \le m, ] where (\text{son}(i)) is the number of children attached to node (i) after deletions. Note that when a node is deleted (except the root, which cannot be deleted), its cherry blossoms and its children are re‐attached directly to its nearest non‐deleted ancestor (its parent if the parent is kept, otherwise further up). The deleted node itself does not contribute to the load of any node.

Your task is to compute the maximum number of nodes that can be deleted (with the root never being deleted) such that after the reattachment process every remaining node (i) satisfies the load constraint (\text{son}(i) + c_i \le m).

Note: All formulas are given in (\LaTeX) format.

inputFormat

The input is given as follows:

The first line contains two integers (n) and (m), where (n) is the number of nodes and (m) is the maximum load permitted.

The second line contains (n) integers: (c_0, c_1, \ldots, c_{n-1}), where (c_i) is the number of cherry blossoms at node (i).

Then follow (n-1) lines. The (i)th of these lines (for (i=1,2,\dots,n-1)) contains a single integer (p_i) which is the parent of node (i) (guaranteed that the tree is rooted at node (0)).

outputFormat

Output a single integer: the maximum number of nodes that can be deleted under the constraints.

sample

5 5
1 0 2 1 0
0
0
1
1

2