P3478 题解 & 换根 dp 学习笔记

Carrot-Meow / 2024-09-23 / 原文

换根 dp，又叫二次扫描，属于树形 dp 的范畴。一般具有一下几个特点：

当指定的根节点不同时，题目求解的答案不同。
在转移期间需要不止一个节点的信息。
需两次 dfs，第一次为预处理，第二次为 dp 过程。

预处理

本题需要记录每个节点的两个信息：

节点 $u$ 的深度 $d_u$。
当树根为 $1$ 时，以节点 $u$ 为根的子树的节点数 $\mathit{sz}_u$。易得 $\mathit{sz}_u = 1 + \sum_{v \in \operatorname{son}(u)} \mathit{sz}_v$。

换根 dp

令 $f_u$ 为以 $u$ 为根时所有节点的深度之和。$\forall v \in \operatorname{son}(u)$，将原来的「以 $u$ 为根」转移到「以 $v$ 为根」。

考虑原来是 $v$ 以及 $v$ 的后代的节点，它们的深度将减少 $1$。而其他节点的深度会增加 $1$。故得转移方程：

\[f_v = f_u - \mathit{sz}_v + n - \mathit{sz}_v \]

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

constexpr int N = 1e6 + 10;
int n, u, v, d[N], sz[N], f[N];
vector<int> tr[N];

// 初始化
void init(int u, int fa = 0) {
    d[u] = u == 1 ? 0 : d[fa] + 1;
    sz[u] = 1;

    for (int i : tr[u])
        if (i != fa) {
            init(i, u);
            sz[u] += sz[i];
        }
}

// 换根 dp
void dp(int u, int fa = 0) {
    for (int i : tr[u])
        if (i != fa) {
            f[i] = f[u] - sz[i] + n - sz[i];
            dp(i, u);
        }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        tr[u].emplace_back(v);
        tr[v].emplace_back(u);
    }

    init(1);

    f[1] = accumulate(d + 1, d + n + 1, 0ll);
    dp(1);

    cout << max_element(f + 1, f + n + 1) - f;
}