P4107 [HEOI2015] Rabbits and Sakura

A long time ago, a group of rabbits lived in a forest. One day, they suddenly decided to go see sakura. The sakura tree in their forest is special. It consists of $n$ branch fork points, numbered from $0$ to $n-1$. These $n$ fork points are connected by $n-1$ branches, and we can regard it as a rooted tree where node $0$ is the root. Each node of the tree has some cherry blossoms; specifically, node $i$ has $c_i$ blossoms. Every node of the sakura tree has a maximum load $m$. For each node $i$, the sum of the number of its children and the number of blossoms on node $i$ must not exceed $m$, i.e., $son(i) + c_i \leq m$, where $son(i)$ denotes the number of children of $i$. If $i$ is a leaf, then $son(i) = 0$. Now the rabbits think there are too many nodes on the sakura tree and want to remove some nodes. When a node is removed, the blossoms on this node and all its children are attached to the parent of the removed node. If the parent is also removed, they continue to attach upward until the first node that is not removed. The rabbits want to compute the maximum number of nodes that can be removed without violating the maximum load. Note that the root cannot be removed, and deleted nodes are not counted toward the load.

The first line contains two positive integers, $n$ and $m$, denoting the number of nodes and the maximum load. The second line contains $n$ integers $c_i$, where $c_i$ is the number of blossoms on node $i$. Then follow $n$ lines. In each line, the first number $k_i$ is the number of children of this node, followed by $k_i$ integers giving the indices of its children.

Output a single integer: the maximum number of nodes that can be removed.

- For $30\%$ of the testdata, $n \leq 5 \times 10^3$, $m \leq 100$, $c_i \leq 100$. - For $70\%$ of the testdata, $n \leq 2 \times 10^5$, $m \leq 2 \times 10^3$, $c_i \leq 10^3$. - For $100\%$ of the testdata, $1 \leq n \leq 2 \times 10^6$, $1 \leq m \leq 10^5$, $0 \leq c_i \leq 10^3$. It is guaranteed that initially, for every node, the sum of its number of blossoms and its number of children is greater than $0$ and does not exceed $m$. Translated by ChatGPT 5