P6122 [NEERC 2016] Mole Tunnels

The moles have dug $n$ burrows underground, connected by $n-1$ tunnels. For any $i>1$, there is a tunnel between burrow $i$ and burrow $\lfloor \frac{i}{2}\rfloor$. Burrow $i$ contains $c_i$ units of food, which can feed at most $c_i$ moles. There are $m$ moles in total, and the $i$-th mole lives in burrow $p_i$. One morning, the first $k$ moles wake up, while the remaining $m-k$ moles are asleep. The first $k$ moles start looking for food. In the end, each of them will arrive at some burrow, such that for every burrow, $c_i$ is greater than or equal to the number of awake moles in that burrow. The total length of all moles’ movement paths must be minimized. For all $1 \le k \le m$, output the minimum possible total length of the moles’ movement paths. It is guaranteed that there is always a feasible solution.

The first line contains two integers $n,m$, meaning there are $n$ burrows and $m$ moles. The second line contains $n$ integers $c_i$, representing the amount of food in burrow $i$. The third line contains $m$ integers $p_i$, where $p_i$ is the burrow where the $i$-th mole is located.

Output one line with $m$ integers. The $i$-th integer denotes the minimum total length of the moles’ movement paths when $k=i$.

For all testdata: $1 \le n,m \le 10^5$, $0 \le c_i \le m$, $1 \le p_i \le n$. Translated by ChatGPT 5