Re-rooting Technique and Global Path Optimization in Tree Dynamic Programming

Core Logic and Mathematical Principles

In the advanced form of Tree Dynamic Programming (Tree DP), the Re-rooting technique (Re-rooting / Up-and-Down Tree DP) is specifically designed to solve the "Global Tree Path Topology Problem".

In standard Tree DP, we typically assume a fixed node (such as node $1$) as the root. In this case, the state can only backtrack contributions along the topology axis from bottom to top (from child nodes to parent nodes). If the problem requires calculating the global statistics for each node in the tree as its own root (e.g., the sum of distances from all nodes to node $i$ when node $i$ is the root), running a DFS of $O(N)$ for each node would result in a disastrous complexity of $O(N^2)$.

The Re-rooting technique allows us to utilize two scans to map the global state without loss in linear time $O(N$) by leveraging the topological shifts of local states.

1. First Scan: Bottom-to-Up

• Geometric Mapping: Choose any node (usually node $1$) as the initial root.

• Physical Semantics: Perform a standard DFS to compute two core topological contribution quantities:

  • $size[u]$: the total number of nodes in the subtree rooted at $u$.
  • $f[u]$: the sum of distances from all nodes in the subtree rooted at $u$ to $u$.

• Backtracking Recursion: After the state of child node $v$ is solidified, pass the contributions to parent node $u$:

$$size[u] = 1 + \sum_{v \in \text{son}(u)} size[v]$$

$$f[u] = \sum_{v \in \text{son}(u)} (f[v] + size[v])$$

2. Second Scan: Up-to-Down (Re-rooting Evolution)

• Geometric Mapping: Let the global total distance when the current node is the root of the entire tree be $g[u]$ (initially, $g[1] = f[1]$). Now, we want to forcibly shift the geometric center of the tree from parent node $u$ to its direct child node $v$.

• State Differential Topological Evolution: When the root changes from $u$ to $v$, the geometric topology of the entire tree undergoes the following mutations:

  • All nodes in the subtree originally belonging to $v$ (a total of $size[v]$ nodes) will have their distances to the new root decreased by 1 due to the proximity of the root node.
  • All nodes outside the subtree of $v$ (a total of $N - size[v]$ nodes) will have their distances to the new root increased by 1 due to the distance from the root node.

• Mathematical Reduction (Re-rooting Equation):

$$g[v] = g[u] - size[v] + (N - size[v]) = g[u] + N - 2 \cdot size[v]$$

With this $O(1)$ algebraic differential equation, we can directly compute the true statistics when child node $v$ is the global root during the second DFS progressing from top to bottom along the edges.

State Design and Algorithm Derivation

1. State Space Definition

• $size[u]$: the size of the subtree rooted at node $u$ when node $1$ is the global root.
• $f[u]$: the local distance contribution from the subtree of node $u$ when node $1$ is the global root.
• $g[u]$: the final total distance from all nodes to node $u$ when $u$ is the geometric root of the entire tree (i.e., the ultimate target state axis).

2. Topological Propagation Control Matrix

• First Round dfs_down(u, fa): Post-order traversal. Leaves bounce back after reaching the bottom, using $f[v]$ and $size[v]$ to update $f[u]$ and $size[u]$.
• Second Round dfs_up(u, fa): Pre-order traversal. Before recursively descending into child nodes, utilize the already formed global state $g[u]$ of the parent node to directly activate the global state $g[v]$ of the child node using the re-rooting equation, then recursively enter $v$.

C++ Standard Source Code (NOIP Style)

The following source code solves the classic global tree path sum problem: "Find which node in the tree minimizes the sum of distances from all nodes to it when it is the root, and output that minimum value," strictly compatible with Linux g++ -O2 compilation standards.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200005;

int n;
vect...  // Omitted intermediate parts

    cout << min_dist << "\n";

    return 0;
}

NOIP Practical Pitfall Guide

1. Pre-order and Post-order Position Reversal in the Second Scan

• Phenomenon: In the second round dfs_up, contestants wrote the re-rooting equation after the recursive call:

  // Incorrect Example
  dfs_up(v, u);
  g[v] = g[u] + n - 2 * size_tree[v]; 

This will cause the current branch to use the initial unassigned 0 or dirty data for child node $v$ and all its descendants during the downward recursion. The global state grid will collapse completely when the recursion returns.

• Avoidance Method: The second round of the re-rooting method is a standard top-to-bottom (pre-order traversal position). You must first calculate the global solution for the current child node using the parent node state, and then allow the recursive instruction to proceed.

2. Re-rooting Multiplication Overflow and Incorrect Constant Coefficient Signs

• Phenomenon: The decrement and increment terms in the equation are reversed, mistakenly written as g[v] = g[u] - (n - size_tree[v]) + size_tree[v]. Or when the total number of nodes $N \ge 10^5$, the total distance will exceed $2 \times 10^9$, and intermediate calculations using the standard int lead to integer overflow (Integer Overflow) turning negative.
• Avoidance Method: Since tree re-rooting involves large-scale integer accumulation, all arrays and local variables storing distances, weights, and subtree sizes must use long long in the exam.

Classic NOIP/Luogu Real Problems

1. Luogu P3478 [STA-Station]

• Problem Description: Given a rootless tree with $N$ nodes, construct a rooted tree such that the sum of the depths of all nodes is maximized. The depth is defined as the number of edges on the simple path from the node to the root. $N \le 10^6$.
• Essence of the Problem and Solution Idea: A textbook-level re-rooting DP template problem.
• Core Idea: The number of edges from nodes to the root is the distance. Fully apply the re-rooting model derived above. The first DFS calculates the sum of depths of all nodes when node $1$ is the root, and the second pre-order DFS uses $g[v] = g[u] + N - 2 \cdot size[v]$ to linearly derive the global solution. Finally, an $O(N)$ scan selects the node number corresponding to the maximum value. Since the data volume reaches $10^6$, be sure to optimize efficiency by using ios_base::sync_with_stdio(false) to unlock I/O locks.

2. Luogu P2986 [USACO10MAR] Great Cow Gathering G

• Problem Description: There are $N$ barns connected by $N-1$ undirected roads forming a tree. Each barn contains $C_i$ cows. Now, all cows need to be gathered in one barn for a meeting. Each road has a specific length $L_i$. The total movement cost generated by cows traversing a road = number of cows $\times$ length of the road. Determine which barn minimizes the total movement cost when gathering all cows.
• Essence of the Problem and Solution Idea: A re-rooting technique specialized for weighted trees with point weights and edge weights.
• Core Idea: Point weights are the number of cows, and edge weights are the lengths of the roads.
• State Correction:
  1. In the first scan from bottom to top: $size[u]$ changes to the total number of cows in the subtree rooted at $u$ (i.e., the sum of point weights in the subtree). $f[u] = \sum (f[v] + size[v] \cdot \text{len}(u, v))$.
  2. In the second scan from top to bottom: Let the total number of cows be $ ext{TotalCow}$. When the meeting place shifts from parent node $u$ to child node $v$, the edge connecting them has weight $W$. The cows inside the subtree of $v$ walk less by distance $W$, while those outside walk more by distance $W$.
  3. Specialized re-rooting equation:

$$g[v] = g[u] - size[v] \cdot W + (\text{TotalCow} - size[v]) \cdot W$$

By elevating simple node counting to weight counting, this perfectly solves the rapid localization of the centroid in weighted trees.