Skip to content

换根 DP

2021-10-28

简介

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

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

分析

d[u]:(以 1 为树根时)u 的深度。

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]size[3]+(nsize[3])

进一步地,设 uv 的父节点,则

f[v]=f[u]size[v]+(nsize[v])

先假定 1 为树根,用 树形 DP 推出 size 数组和 d 数组;再用换根 DP 推出 f 数组,并取最大值。

边界条件为 f[1]=d[i],时间复杂度为 O(n)

cpp
// 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;
}