Handling Multiple Children (Prefix-suffix pattern)

Node $u$ has children $c_1, c_2, \ldots, c_k$. To compute up[c_i], you need the combined contribution of all children except $c_i$. Naively recomputing this for each child takes $O(k^2)$ time. Build prefix array: pref[i] = combine(down[c_1], ..., down[c_i]). Build suffix array: suff[i] = combine(down[c_i], ..., down[c_k]).

These take $O(k)$ time to build. Then for child $c_i$, the contribution of other children is combine(pref[i-1], suff[i+1]). You get all $k$ values in $O(k)$ total time. This only works when combine is associative.

Space complexity is $O(n)$ for the data structures used.