Up Pass (Propagating parent contributions)

The second DFS propagates contributions from the parent side. For each node $v$ with parent $u$, you compute up[v]: the answer contribution from everything outside $v$'s subtree.

To get up[v], start with up[u] (what $u$ sees from its parent side), then add contributions from all of $u$'s children except $v$. This gives $v$ the full picture of the tree beyond its own subtree.

The root has no parent, so up[root] = 0. Every other node inherits and extends its parent's $up$ value. This pass also runs in $O(n)$ time and uses $O(n)$ space.