Rerooting Dynamic Programming

Rerooting computes related answers for every vertex without solving the tree from scratch each time. For sum of unweighted distances, we first collect subtree sizes and root-distance contributions, then propagate answers across edges. The two passes are iterative equivalents of bottom-up and top-down DFS. The key transition explicitly accounts for vertices outside the child subtree.

Prerequisites: Tree DP; Subtree Sizes; Rerooting DP in Trees. Related existing lessons: Rerooting DP.

Build the idea

1. Recognize the repeated subproblems

   Running BFS from all n vertices costs O(n²) on a tree. Neighboring-root answers differ predictably:when crossing one edge, some vertices become one step closer and the others one step farther. A first rooted computation identifies the size of those two groups, allowing constant-time reuse per edge.

2. Define the state

   Fix root 1. size[u] counts vertices in u’s fixed rooted subtree, and down[u] sums distances from u to those vertices. answer[u] is the desired sum from u to every vertex, not just its subtree. Keep the fixed-root size definition throughout the second pass; changing its meaning mid-reroot would break the transition.

3. Derive the transition

   Bottom-up, each child v contributes size[v] vertices and down[v]+size[v] distance to its parent. Therefore down[1] is answer[1]. Moving the root from u to child v makes size[v] vertices one step closer and n−size[v] one farther. Add their signed changes:answer[v]=answer[u]+n−2·size[v]. No subtraction of down[v] alone captures all outside contributions.

   $$\mathrm{answer}\left[v\right]=\mathrm{answer}\left[u\right]+n-2·\mathrm{size}\left[v\right]$$

4. Base cases and computation order

   Build parent-before-child order from root 1. Reverse it to accumulate size and down, then use it forward to propagate answer from each known parent to its children. Start size=1 and down=0 for singleton subtrees. A singleton tree has answer zero. The fixed parent array prevents revisiting the undirected parent edge.

5. Correctness and invariant

   Induction on the reverse order proves the subtree aggregates. The root answer covers the entire tree. For each edge, the two vertex groups partition all n vertices, so the exact +1/−1 distance changes prove the reroot transition. Forward induction then establishes every global answer. This special arithmetic is a simple rerooting instance; general states may need prefix/suffix child combinations rather than one size formula.

6. Work the example

   Path 1–2–3 rooted at 1 has subtree sizes 3,2,1 and down values 3,1,0. answer[1]=3. Crossing to vertex 2 gives 3+3−4=2; crossing to vertex 3 gives 2+3−2=3. Output 3 2 3. The outside contribution at a leaf is most of its answer, so subtree sums alone are insufficient.

   vertex	fixed size	down	global answer
   1	3	3	3
   2	2	1	2
   3	1	0	3

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

#include<iostream>
#include<vector>
int main(){
    int n;
    std::cin>>n;
    std::vector<std::vector<int>>tree(n+1);
    for(int i=1;i<n;++i){
        int u,v;
        std::cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    std::vector<int>parent(n+1),order{1},size(n+1,1);
    std::vector<long long>down(n+1),answer(n+1);
    for(int i=0;i<(int)order.size();++i){
        for(int v:tree[order[i]]){
            if(v!=parent[order[i]]){
                parent[v]=order[i];
                order.push_back(v);
            }
        }
    }
    for(int i=n-1;i>0;--i){
        int u=order[i],p=parent[u];
        size[p]+=size[u];
        down[p]+=down[u]+size[u];
    }
    answer[1]=down[1];
    for(int u:order){
        for(int v:tree[u]){
            if(parent[v]==u){
                answer[v]=
                    answer[u]+n-2LL*size[v]; // Subtree vertices get one closer; all others one farther.
            }
        }
    }
    for(int u=1;u<=n;++u){
        std::cout<<answer[u]<<(u==n?'\n':' ');
    }
}

Complexity analysis

O(n) states/edges across two passes, so O(n) time and O(n) adjacency/traversal storage. Answers can reach n(n−1)/2 on a path endpoint and require long long; subtree counts fit int. No repeated BFS or recursive deep-chain stack is used.

Example input and output

Read n (1..200000), then n−1 edges of a valid connected unweighted tree, vertices 1..n. Print sum of distances from each vertex to all vertices, in ID order.

Input

3
1 2
2 3

Output

3 2 3

Path 1–2–3 rooted at 1 has subtree sizes 3,2,1 and down values 3,1,0. answer[1]=3. Crossing to vertex 2 gives 3+3−4=2; crossing to vertex 3 gives 2+3−2=3. Output 3 2 3. The outside contribution at a leaf is most of its answer, so subtree sums alone are insufficient.

Practical applications

Use when answers for different roots share almost all subproblems. The existing Trees rerooting lesson is related; this DP lesson centers the state meanings and two-direction dependency order. General associative rerooting often needs excluding one child’s contribution efficiently.

Check your understanding

How many vertices become farther when moving from u to its child v?

Put it into practice

Compare all answers with one BFS from each vertex on small trees.