Node has children . To compute up[c_i], you need the combined contribution of all children except . Naively recomputing this for each child takes 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 time to build. Then for child , the contribution of other children is combine(pref[i-1], suff[i+1]). You get all values in total time. This only works when combine is associative.
Space complexity is for the data structures used.