树形DP - 换根

换根DP的基本思路

所谓“换根”，指的是这样一种特定的解树上题目的技巧：

1. 固定一个方便计算的根的位置，然后DP计算题目需要的答案。
2. 计算将根移动到孩子处的时候，答案会怎样变化。然后DFS将根移动到所有位置，求最优结果。

这样的主要好处，是“换根”过程是利用树的结构的一个过程，使得之前的计算结果可以重用，降低复杂度。

题解 - Tree Painting

观察此题，首先可以看到第一个点选在哪里是比较关键的，因为后面的点必须和这个点相邻。实际上第一个点选定之后，最终的得分就确定了。

如果我们把第一点看成是树的根的话，设每个节点$i$的子树大小是$S_i$，可以得到整根树的总分是$\sum_i S_i$.

比较直观的想法，是对每个节点做这个计算，取最大值就得到了最后的答案。但是因为$n \leq 2 \cdot 10^5$，这个$\mathcal{O}(n^2)$的算法太慢了。

所以我们考虑用换根DP：

1. 不失一般性，我们称把根固定在节点$0$处，从这里开始画黑色节点，得到总分为$f_0 = \sum_i S_i$.
2. 假设$f_i$已知，我们移动根到$i$的孩子$u$处，那这时一些$S_i$会发生变化，我们想办法算出$f_u$。
3. 具体而言，我们看到只有$S_i$和$S_u$发生变化，如下图所示：

         i                      u
        / \                   / | \
       u   ...    ==>   (不变)...   i
      / \                          |
      ...                          ... (不变)
   

   因此我们有：
   $$\begin{align} S'_u &= S_u + (n-S_u) \\ S'_i &= S_i - S_u \\ f_u &= f_i + (S'_u-S_u) + (S'_i-S_i) \\ &= f_i + n - 2 \cdot S_u \end{align}$$

利用最后(4)这个公式，可以一遍DFS算出所有的$f_i$，取最大值就是答案了。最终的复杂度是$\mathcal{O}(n)$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
vector<int> adj[200005];
int S[200005];
ll f[200005];
 
void dfs1(int s, int e) {   // 计算f[0]
    S[s] = 1;
    for (int u: adj[s]) {
        if (u == e) continue;
        dfs1(u, s);
        S[s] += S[u];
    }
    f[0] += S[s];
}
 
void dfs2(int s, int e) {   // 基于f[0], 计算所有的f[s]
    if (s != 0)
        f[s] = f[e] + n - 2*S[s];
    for (int u: adj[s]) {
        if (u == e) continue;
        dfs2(u, s);
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n-1; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(0, -1);
    dfs2(0, -1);
    ll ans = *max_element(f, f+n);
    printf("%lld", ans);
 
    return 0;
}

习题