Re-rooting DP is a tree-DP variant that looks intimidating at first, yet becomes very mechenical once the pattern is recognized. The following problems illustrate the key techniques.

Problem 1 – USACO 2012 FEB "Nearby Cows"

Task: for every node i compute the sum of weights of all nodes whose distance to i is at most K.

Constraints: n ≤ 1e5, K ≤ 20.

State: down[u][d] – sum of weights in the subtree of u at distance ≤ d when the tree is rooted at 1.

First DFS:

down[u][d] = c[u] + Σ down[v][d-1]   (v is a child of u, d ≥ 1)
down[u][0] = c[u]

Re-rooting: when moving the root from u to its child v we need the contribution that u receives from the rest of the tree. That contribution is exactly up[u][d-1] where

up[v][d] = down[u][d] - down[v][d-1]

and the new answer for v is

ans[v][d] = down[v][d] + up[v][d]

By processing d in descending order we can overwrite the down array in place:

for d = K .. 2
    down[v][d] += down[u][d-1] - down[v][d-2]

Problem 2 – AtCoder DP Contest "Subtree"

Task: for every node compute the number of subsets of its subtree that contain the node itself, modulo m (not necessarily prime).

State: f[u] – number of valid subsets in the subtree of u when u is taken.

First DFS:

f[u] = ∏ (f[v] + 1)   (v is a child of u)

Re-rooting without inverce: store prefix and suffix products of f[v]+1 for every node, then

prefix[i] = prefix[i-1] * (f[v_i]+1)
suffix[i] = suffix[i+1] * (f[v_i]+1)
rest = prefix[i-1] * suffix[i+1] * up[u] + 1
f'[v_i] = f[v_i] * rest

up[u] is the contribution from above u computed in the same fashion.

Problem 3 – COCI 2014/2015 Kamp

Task: for every node compute the minimal total length of a walk that starts at i and visits all marked vertices.

Observation: the optimum walk is twice the total edge length of the minimal subtree containing all marked vertices minus the depth of the deepest visited vertex.

Steps:

1. Shrink the tree to the minimal subtree that contains every marked vertex.
2. Let deep[u] be the maximum depth in the subtree of u (fixed root). Compute it with one DFS.
3. Re-root: for an edge u→v the new maximum depth below v is either deep[v] or maxDeepOutside[u]+1. Maintain maxDeepOutside with the usual max/second-max trick.
4. Non-shrunk vertices simply copy the answer of their nearest shrunk ancestor plus the extra path length.

Problem 4 – APIO 2014 "Beads"

State: two values per node

• dp[u][0] – maximum score when u is an endpoint of a blue chain.
• dp[u][1] – maximum score when u is the middle of a blue chain.

First DFS:

dp[u][0] = Σ max(dp[v][0], dp[v][1]+w)
dp[u][1] = dp[u][0] + max_v (dp[v][0] - max(dp[v][0], dp[v][1]+w))

Re-rooting: when moving the root from u to v we need

• the contribution of u without v (prefix/suffix or max/second-max),
• the contribution from above u (stored in up[u][0/1]),
• merge these pieces to obtain dp'[v][0/1].

All arrays can be overwritten in place by processing children in reverse order. ### Problem 5 – CF1796E "Colored Subgraphs"

Goal: choose a root so that the shortest chain in the heavy-light decomposition is as long as possible.

First DFS: compute for every node u

• len[u] – length of the chain ending at u (min over children plus one).
• shortest[u] – shortest chain completely inside the subtree of u (min of len[u] and all shortest[v]).

Re-rooting: maintain

• upLen[u] – length of the chain coming from the parent side,
• upShort[u] – shortest chain outside the subtree of u.

These value are updated with the usual min/second-min technique. The answer for root r is min(len[r], shortest[r]). Recipe for Re-rooting DP

1. Fix a root and solve the problem for that root with a post-order DFS.
2. Re-root with a second DFS:
   • remove the contribution of the child you are moving into,
   • add the contribution from the parent side,
   • recurse into the child,
   • restore the arrays for siblings.
3. Compress arrays whenever the new answer for a node can be computed from its own subtree information plus a single "outside" value.

Typical indicators:

• "For every node compute …" with n ≤ 1e5.
• Problem becomes easy once the root is fixed.
• Contribution removal is possible via inverse operations or min/max/second-max bookkeeping.