Rerooting DP

Compute a tree DP answer for every possible root in $O(n)$ total, instead of $O(n^2)$ by re-running the DFS from each vertex.

The problem it solves

“For each vertex $v$, what is the sum of distances from $v$ to all others?” — or the maximum depth, or the number of paths, or any quantity a tree DP computes for a fixed root.

The two passes

Pass 1 (down). A normal tree DP rooted anywhere. down[u] = the answer for $u$‘s subtree.

Pass 2 (up). Push information from parents to children. up[v] = the answer for the part of the tree outside $v$‘s subtree, as seen from $v$.

$\text{answer}[v]=\mathrm{combine}(\mathrm{down}[v],\mathrm{up}[v]).$

Worked example: sum of distances

vector<long long> down, up, sz;
 
void dfs1(int u, int p) {
    sz[u] = 1; down[u] = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        down[u] += down[v] + sz[v];        // each vertex in v's subtree is 1 further
    }
}
 
void dfs2(int u, int p) {
    for (int v : adj[u]) {
        if (v == p) continue;
        // everything not in v's subtree, measured from v
        up[v] = up[u] + (down[u] - down[v] - sz[v]) + (n - sz[v]);
        dfs2(v, u);
    }
}
// answer[v] = down[v] + up[v]

The line computing up[v] is the heart of it: take $u$‘s total, subtract $v$‘s contribution, add $u$‘s own outside part, then account for the extra step from $u$ to $v$.

When subtraction is impossible

The pattern above needs to “remove one child’s contribution”. That is easy for sums but impossible for max, min, gcd or any non-invertible combine. The fix is prefix and suffix aggregates over the children:

void dfs2(int u, int p) {
    int k = adj[u].size();
    vector<long long> pre(k + 1, IDENTITY), suf(k + 1, IDENTITY);
    for (int i = 0; i < k; i++)
        pre[i+1] = merge(pre[i], contribution(adj[u][i], u));
    for (int i = k - 1; i >= 0; i--)
        suf[i] = merge(suf[i+1], contribution(adj[u][i], u));
 
    for (int i = 0; i < k; i++) {
        int v = adj[u][i];
        if (v == p) continue;
        long long without = merge(pre[i], suf[i+1]);      // all children except v
        up[v] = lift(merge(without, up[u]), u, v);
        dfs2(v, u);
    }
}

$O(\mathrm{deg}u)$ per vertex, so $O(n)$ overall. This version works for any associative combine, and is the general form worth memorising.

For max specifically, a lighter alternative is to keep the two largest child values; removing one child is then “use the largest, unless it came from this child, in which case use the second largest”.

The recipe

1. Define down[u] — the answer restricted to $u$‘s subtree.
2. Write combine(a, b) and the identity element.
3. Write lift(value, u, v) — how a value at $u$ transforms when moved to child $v$ (usually “add the edge weight” or “add 1”).
4. Pass 1: compute down bottom-up.
5. Pass 2: compute up top-down using prefix/suffix aggregates.
6. answer[v] = combine(down[v], up[v]).

What it computes for every root

Quantity	down	combine
Sum of distances	sum over the subtree	+, lifting adds sz
Maximum distance (eccentricity)	max depth	max, lifting adds 1
Number of paths through $v$	product of counts	*
Longest path ending at $v$	max chain	max
Number of subtrees containing $v$	product of $(1+\text{child})$	*
Best answer when $v$ is the root	any tree DP	as defined

Eccentricity for every vertex is the most common use, and it is worth noting the shortcut: on a tree, $\mathrm{ecc}(v)=\max (\mathrm{dist}(v,A),\mathrm{dist}(v,B))$ where $A,B$ are diameter endpoints — two BFS runs, no rerooting needed. Use rerooting for quantities without such a shortcut.

See also: Tree DP · Tree Diameter · Tree Fundamentals