First build the full tree and make centroid decomposition there. The centroid decomposition is built by selecting one central node as root node, removing it from the original tree and then recursively building the decomposition on each of the now-disjoint components. Each node has O(log n) ancestors in the central decomposition. While building the decomposition, store distances from every node to each of its ancestors.

After building the central decomposition, start making nodes active in the order they were given in the input. In this phace maintain in each node of the centroid decomposition the number of active nodes in the subtree and the sum of their distances to the root of the subtree. When a node becomes active, update all its ancestors in the decomposition using the precomputed distances.

By maintaining these values, we can also compute the sum of distances of a node to every other active node, which is what is asked in the problem statement. Say we want to compute the sum of distances from node x to all other nodes. We compute the distances separately in each of the O(log n) subtrees of the centroid decomposition containing x. Let y be an ancestor of x. Then the nodes in the subtree rooted at y can be divided to two parts:

• The nodes in the subtree containing x. The distances to those nodes are computed recursively in that subtree.

• The nodes in different subtrees than x. Any path from x to them goes trough y, so the sum of distances can be computed using the aforementioned sum values maintained in each node.

So basically first compute the distances to all nodes in the subtree rooted at x. Then go to the parent node of x, and compute the distances to all nodes in its subtree that are not in x's subtree, and keep going up until you reach the root node.