简介

换根 DP 是基于 树形 DP 的更高效算法。通常设 $f[u]$ 表示以 $u$ 为树根时的解，进而从推出 $f[$其它节点$]$。

例

给定一棵 $n$ 个点的树，请求出一个节点，使得以其为根时，所有节点的深度之和最大（根节点的深度为 $1$）。

分析

$d[u]$：（以 $1$ 为树根时）$u$ 的深度。

$\mathrm{size}[u]$：（以 $1$ 为树根时）以 $u$ 为根的子树的节点数。

$f[u]$：以 $u$ 为树根时的节点深度和。

以 $1$ 为根时：

flowchart
A(($$1$$))
B(($$2$$))
C(($$3$$))
D(($$4$$))
E(($$5$$))
F(($$6$$))
G(($$7$$))
H(($$8$$))
A --> B & C
B --> D & E
C --> F & G & H

以 $3$ 为根时：

flowchart
A(($$1$$))
B(($$2$$))
C(($$3$$))
D(($$4$$))
E(($$5$$))
F(($$6$$))
G(($$7$$))
H(($$8$$))
C --> A & F & G & H
A --> B --> D & E

观察发现，原先 $3$ 的子树中（包括 $3$）节点的深度减少了 $1$，而其余节点的深度增加了 $1$。因此

$$f[3]=f[1]-\mathrm{size}[3]+(n-\mathrm{size}[3])$$

进一步地，设 $u$ 是 $v$ 的父节点，则

$$f[v]=f[u]-\mathrm{size}[v]+(n-\mathrm{size}[v])$$

先假定 $1$ 为树根，用 树形 DP 推出 $\mathrm{size}$ 数组和 $d$ 数组；再用换根 DP 推出 $f$ 数组，并取最大值。

边界条件为 ${\displaystyle f[1]=\sum d[i]}$，时间复杂度为 $O(n)$。

// g[u]: 与 u 相连的点的集合
vector<int> g[];

void dfs1(int u, int fa) {
    size[u] = 1;
    d[u] = d[fa] + 1;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        size[u] += size[v];
    }
}

void dfs2(int u, int fa) {
    for (int v : g[u]) {
        if (v == fa) continue;
        f[v] = f[u] - size[v] + (n - size[v]);
        dfs2(v, u);
    }
}

int main() {
    dfs1(1, 0);
    for (int i = 1; i <= n; i ++)
        f[1] += d[i];
    dfs2(1, 0);
    for (int i = 1; i <= n; i ++)
        maxn = max(maxn, f[i]);
    cout << maxn;
}