Zhora the Vacuum Cleaner

The expensive-looking operation is not expensive per nut. It costs $p$ once and sends a whole wave of nuts toward the chosen vertex. So forget total moved distance; that idea dies instantly on the samples.

Start with one edge. Remove edge $xy$, and let $C_{x\to y}$ be the component containing $y$. Define

$$S_{x\to y}=\sum_{u\in C_{x\to y}} a_u.$$

Suppose every future movement operation is chosen somewhere on the $x$-side of the edge. As long as the $y$-side still contains at least one nut, vertex $y$ will have a nut by the time it is processed: either it already had one, or some deeper vertex passed one into it. Then $y$ sends exactly one nut across edge $xy$. So the total number of nuts on the $y$-side drops by exactly $1$ per operation until it reaches $0$.

Therefore, the $y$-side disappears after exactly

$$S_{x\to y}$$

operations. That is the key invariant. No distance sum. No per-edge payment. Just one nut crossing the boundary per wave.

For a vertex $v$, ask how early it can be made empty by pushing it through one of its incident edges. If we remove edge $uv$ and choose operations from the $u$-side, the whole component containing $v$ disappears after the number of nuts in that component. So the raw disappearance time is

$$\min_{u\in adj(v)} S_{u\to v},$$

where $S_{u\to v}$ is the nut-sum of the component containing $v$ after removing edge $uv$.

There is one annoying zero-vertex detail. If $a_v=0$, remove $v$ and count how many neighboring components contain nuts. If this count is at most $2$, then $v$ is just an empty pipe or outside the useful nut structure. It can be treated as already empty forever, so set

$$z_v=0.$$

If that count is at least $3$, then several branches can send nuts into $v$ while it forwards only one nut, so it may become non-empty. For that vertex, keep the raw value. For positive vertices, also keep the raw value.

Now define all final values $z_v$ this way.

Next, why does sorting these values solve the whole problem? Think about choosing one final surviving vertex $r$ and applying all movement operations toward it. Pick $r$ as a weighted centroid of the tree using nut counts: every component adjacent to $r$ has at most half of the total nuts. Equivalently, $r$ maximizes the minimum component-sum value above.

For any other vertex $v$, the neighbor on the path from $v$ to $r$ lies in the largest nut-containing direction from $v$. Otherwise some branch away from $r$ would contain more nuts than the side toward $r$, contradicting the centroid choice. Thus the component of $v$ away from $r$ has exactly size $z_v$, and by the edge invariant it disappears after $z_v$ operations toward $r$.

So after $k$ movement operations toward this survivor, every vertex with $z_v\le k$ can be made empty, except that at least one vertex must remain non-empty because there is still a positive total number of nuts. Conversely, if $z_v>k$, no sequence of only $k$ operations can force $v$ to be empty: every incident cut containing $v$ starts with more than $k$ nuts, and at most one nut can leave through the chosen boundary per operation.

There are now only threshold choices.

Doing no movement costs

$$q\cdot |\{v:a_v>0\}|.$$

If we do movements, sort

$$z_1\le z_2\le \dots\le z_n.$$

If exactly $i$ vertices are emptied by movement, where $1\le i<n$, the cheapest required operation count is $z_i$, and $n-i$ vertices remain to eat. The candidate cost is

$$pz_i+q(n-i).$$

Therefore,

$$ans=\min\left(q\cdot |\{v:a_v>0\}|,\ \min_{1\le i<n}\bigl(pz_i+q(n-i)\bigr)\right).$$

Now compute the $z_v$ values.

Root the tree at $1$. Let

$$sub[v]=\sum_{u\in subtree(v)}a_u, \qquad T=\sum_{v=1}^n a_v.$$

For an edge between parent $p$ and child $c$:

• the component containing $c$ has sum $sub[c]$;
• the component containing $p$ has sum $T-sub[c]$.

Use these two values to update the raw minimum for both endpoints.

For the harmless-zero test, we need the neighboring components after deleting a vertex. For the same edge:

• from $p$'s point of view, the child-side neighboring component has sum $sub[c]$;
• from $c$'s point of view, the parent-side neighboring component has sum $T-sub[c]$.

Count how many such neighboring component sums are positive. If $a_v=0$ and that count is at most $2$, force $z_v=0$.

Edge cases:

• If $T=0$, answer $0$.
• If $q=0$, answer $0$.
• If $p=0$ and $T>0$, the formula naturally gives $q$, because all nuts can be gathered to one vertex for free.
• Use long long; totals and costs go way past int.

The DFS work is $O(n)$, and sorting the $z_v$ values costs $O(n\log n)$. Memory usage is $O(n)$.