换根 DP

简介 #

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

例 1 #

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

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

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

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

以 $1$ 为根时：

flowchart
1 --> 2 & 3
2 --> 4 & 5
3 --> 6 & 7 & 8

以 $3$ 为根时：

flowchart
3 --> 1 & 6 & 7 & 8
1 --> 2 --> 4 & 5

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

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

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

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

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

初始条件为 $\displaystyle f[1]=\sum d[i]$，时间复杂度为 $O(n)$.

void dfs1(int u, int fa) {
    size[u] = 1;
    d[u] = d[fa] + 1;
    for (int i = 0; i < g[u].size(); i ++) {
        int v = g[u][i];    // v 是 u 的第 i 个子节点
        if (v == fa) continue;
        dfs1(v, u);
        size[u] += size[v];
    }
}

void dfs2(int u, int fa) {
    for (int i = 0; i < g[u].size(); i ++) {
        int v = g[u][i];
        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;
}