Dynamic Programming with Rerooting (Rerooting DP)

Introduction

Subtree DP gives an answer for one chosen root. Some tree problems, however, ask for the answer when every vertex is treated as the root or starting point.

Running the same DFS independently from all $n$ vertices repeats almost all of the work. Rerooting DP avoids this repetition. It first solves the tree for one root, then moves the root across one edge at a time and updates the answer using the information already known on both sides of that edge.

Rerooting appears in distance problems, best-root problems, tree scores, and DP states that depend on contributions from every direction. By the end of this lecture, we will understand the two DFS passes, derive a reroot transition, and calculate the answer for every vertex in linear time.

Problem or motivation

Given a tree with $n$ vertices, calculate for every vertex $v$ the sum of distances from $v$ to all vertices:

answer [v] = \sum_{u = 1}^{n} dist (v

Dynamic Programming with Rerooting (Rerooting DP)

Introduction

Problem or motivation

Naive approach

Core concept

Main algorithm

Implementation

Complexity