Cost of Tree

Root the tree at $1$. For each node $u$, let

$sum[u]=\sum_{x\in subtree(u)} a_x$

and let $mx[u]$ be the maximum absolute depth of any node in $subtree(u)$.

First compute the cost before any operation. If $base[u]$ is the cost of $subtree(u)$ when rooted at $u$, then every node inside a child subtree $c$ becomes one edge farther when viewed from $u$. Therefore

$base[u]=\sum_{child\ c}(base[c]+sum[c]).$

Now we only need the best possible gain from one operation.

Suppose we detach node $x$ and attach it under node $v$. The whole subtree of $x$ moves together, and every node in it changes depth by

$depth[v]+1-depth[x].$

So the gain is

$sum[x]\cdot(depth[v]+1-depth[x]).$

The dangerous-looking part is that $x$ could be any descendant. Trying all pairs is obviously dead on arrival.

Here is the useful split. For a fixed subtree root $r$, take an optimal operation and let

$w=\operatorname{lca}(x,v).$

Because $v$ must be outside $subtree(x)$, $w$ is a strict ancestor of $x$.

If $w\ne r$, then both $x$ and $v$ lie inside the same child subtree of $r$. That operation is already counted in that child. So those cases are handled by taking the maximum answer among children.

The only new operations created at node $r$ are the ones with $w=r$. Then $x$ lies inside one child subtree $c$, and $v$ lies either at $r$ or inside a different child subtree $d$.

If $v=r$, the gain is never positive. Moving something upward or keeping a direct child where it already was does not help, and we are allowed to do nothing.

So $v$ must be in a different child subtree. For fixed child $c$ containing $x$ and fixed target branch $d$, the deepest possible $v$ in $subtree(d)$ is best. Now comes the main greedy point: the best $x$ inside branch $c$ is just the direct child $c$ itself.

Why? For any descendant $x$ of $c$,

$sum[c]\ge sum[x]$

and

$depth[v]+1-depth[c]\ge depth[v]+1-depth[x].$

The first factor is larger, and the depth gain is also larger. Since moving $c$ under $v$ is legal, moving deeper inside $c$ can never beat it. That false assumption is the whole trap; once you kill it, the problem chills out.

Therefore the best crossing move at $r$ is

$cross[r]=\max_{c\ne d} sum[c]\cdot(mx[d]-depth[r]),$

where $c,d$ are children of $r$. The term comes from

$depth[v]+1-depth[c]=mx[d]+1-(depth[r]+1)=mx[d]-depth[r].$

For each child $c$, we only need the largest $mx[d]$ among the other children. Store the top two child subtree depths, so this is $O(1)$ per child.

Let $best[u]$ be the maximum gain possible inside $subtree(u)$. The recurrence is

$best[u]=\max\left(cross[u],\max_{child\ c} best[c]\right).$

Finally,

$ans[u]=base[u]+best[u].$

Edge cases are clean:

• A leaf has $base=0$ and $best=0$.
• A node with only one child has no positive crossing move at that node.
• A path has no branching anywhere, so every answer is just the original subtree cost.

All values need long long: sums and costs can reach about $8\cdot 10^{15}$.

The algorithm is one root traversal plus one reverse traversal, so the complexity is

$O(n)$

per test case, with $O(n)$ memory.