Prefix-Suffix Arrays (Excluding one child)

When computing up[v] for child $v$ of node $u$, you need the combined contribution of all other children of $u$, excluding $v$. If $u$ has $k$ children, recomputing the combination for each child takes $O(k)$ per child and $O(k^2)$ total.

The fix: build prefix and suffix arrays over $u$'s children. prefix[i] combines children $c_1$ through $c_i$. suffix[i] combines children $c_i$ through $c_k$. To exclude child $c_i$, combine prefix[i-1] with suffix[i+1] in $O(1)$. This keeps the total work per node proportional to its degree, giving $O(n)$ overall.