Rerooting DP

Rerooting DP computes a related tree answer for every possible root without running a fresh traversal N times. One pass gathers information inside subtrees; another passes the missing outside information across each edge. We will calculate ans[v], the sum of unweighted distances from v to all vertices. This is useful for choosing central facilities, comparing possible roots, and understanding how a local change of perspective updates a global quantity.

Prerequisites: Subtree sizes, distance in trees, and bottom-up tree DP.

Build the idea

1. 1. Understand the quadratic baseline. BFS from one vertex finds all its distances in O(N). Repeating that for all N roots costs O(N²). Adjacent roots, however, have closely related distance sums. We need to reuse that relation rather than repeat identical work. Fix root 1 temporarily to define parent, depth, and subtree size. This temporary root is bookkeeping; the final array contains answers for every root.
2. 2. Obtain the first answer and subtree sizes. Traverse once from root 1. The sum of all depth[v] equals ans[1], because unweighted depth is distance from the root. Process vertices in reverse parent-before-child order to get size[v]=1+sum(size[child]). The second pass will use the size of each child side of an edge. These sizes remain relative to the original root; we do not rewrite them every time we derive an answer.
3. 3. Move the root across one edge. Suppose c is a child of p. Removing edge p–c splits the tree into size[c] vertices on c’s side and N−size[c] on p’s side. Moving the reference vertex from p to c makes every vertex on c’s side one step nearer and every other vertex one step farther. Hence ans[c]=ans[p]−size[c]+(N−size[c])=ans[p]+N−2·size[c]. The two sides partition all vertices, including the two endpoints, so no extra correction is needed.
4. 4. Verify the arithmetic by hand. For edges 1–2, 1–3, 2–4, 2–5, distances from 1 are [0,1,1,2,2], totaling 6. The subtree at 2 has size 3, so ans[2]=6+5−6=5. Vertex 3 has size 1, so ans[3]=6+5−2=9. From vertex 2 to child 4, ans[4]=5+5−2=8; vertex 5 also gets 8. The complete answer is [6,5,9,8,8]. Repeating BFS is a useful independent way to check these numbers on small trees.
5. 5. Propagate in the correct order. The first pass needs children before parents to compute sizes. The second pass needs parents before children so ans[parent] is already known. The same stored traversal order supports both directions. Each edge passes information once in each direction conceptually. long long is necessary for large sums: on an N-vertex path an endpoint’s sum is N(N−1)/2, which can exceed a signed 32-bit integer.
6. 6. Generalize the idea without overgeneralizing the formula. For an edge of weight w, the change becomes w·(N−2·size[c]). Other rerooting problems need a different merge rule. If a parent combines child contributions using a function that cannot be inverted, prefix and suffix aggregates let you exclude one child in O(1) after linear preparation. For maximum distances, keeping the largest two child contributions serves the same purpose. Always identify exactly what information comes from the child side and what comes from the rest of the tree.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>>g(n+1);
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int>parent(n+1),depth(n+1),size(n+1,1),order{1};
    for(int i=0;i<(int)order.size();i++){
        int v=order[i];
        for(int u:g[v]){
            if(u!=parent[v]){
                parent[u]=v;
                depth[u]=depth[v]+1;
                order.push_back(u);
            }
        }
    }
    vector<long long>ans(n+1);
    // Root 1 distances equal depths; this supplies the first global answer.
    for(int v=1;v<=n;v++){
        ans[1]+=depth[v];
    }
    // Reverse order makes a child size complete before adding it to its parent.
    for(int i=n-1;i>0;i--){
        int v=order[i];
        size[parent[v]]+=size[v];
    }
    // A parent's answer is ready before its children's answers.
    for(int i=1;i<n;i++){
        int v=order[i];
        // Across this edge, size[v] vertices get nearer; all others get farther.
        ans[v]=ans[parent[v]]+n-2LL*size[v];
    }
    for(int v=1;v<=n;v++){
        cout<<ans[v]<<(v==n?'\n':' ');
    }
}

Complexity analysis

O(N) total time and O(N) auxiliary space. Building order, accumulating depths, accumulating sizes, and propagating answers each scan only O(N) vertices and edges. Running independent BFS from every vertex would take O(N²).

Example input and output

N then N−1 undirected edges. Output the distance sum for vertices 1 through N.

Input

5
1 2
1 3
2 4
2 5

Output

6 5 9 8 8

Moving from 1 to 2 brings three vertices nearer and two farther, decreasing the total by one.

Practical applications

Sum of distances, all-roots optimization, tree eccentricities, weighted facility placement, and DP messages passed along directed edges. Euler tours answer fixed-root subtree queries; rerooting answers a whole family of roots.

Check your understanding

When moving the root from p to child c, how many vertices get one step nearer?

Put it into practice

Adapt the solution to edges with positive integer weights.