树学（换根dp或重心）

题目：

牛妹有一张连通图，由n个点和n-1条边构成，也就是说这是一棵树，牛妹可以任意选择一个点为根，根的深度 $dep_{root}$ 为0，对于任意一个非根的点，我们将他到根节点路径上的第一个点称作他的父节点，例如1为根，1-4的；路径为1-3-5-4时，4的父节点是5，并且满足对任意非根节点 $dep_i=dep_{fa_i}+1$ 。整棵树的价值。 $W=\sum\limits_{i=1}^n dep_i$ 。即所有点的深度和。

牛妹希望这棵树的W最小，请你告诉她，选择哪个点可以使W最小。
对于100%的数据， $1\leq n \leq 10^6$

做法：

有点诡异。
做法1：盲猜最优点在重心上。 $dfs$ 一遍求重心 $rt$ 。从 $rt$ 开始再 $dfs$ 一遍求深度和。做完。
做法2：换根dp。
$dp[u]$ 表示以 $u$ 为整棵树的根的深度和。我们可以一遍 $dfs$ 求出以1为根的深度和。然后从1在 $dfs$ 一遍求出将根转移到子树 $v$ 上的深度和 $dp[v]$ 。
转移： $dp[v] = dp[u]-size[v]+(n-size[v]);$ (size[v]表示子树v的大小)

代码

重心：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
const int inf = 0x3f3f3f3f;
vector<int> g[N];
int n, rt, son[N], size[N], dep[N], ans;
void getrt(int u, int p){
    size[u] = 1, son[u] = 0;
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if (v == p) continue;
        getrt(v, u);
        size[u] += size[v];
        son[u] = max(son[u], size[v]);
    }
    son[u] = max(son[u], n-size[u]);
    if (son[u] < son[rt]) rt = u;
}
void dfs(int u, int p){
    dep[u] = dep[p]+1;
    ans += dep[u];
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if (v == p) continue;
        dfs(v, u);
    }
}
int main(void){
    scanf("%d", &n);
    for (int i = 0; i < n-1; ++i){
        int u, v; scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    rt = 0, son[0] = inf;
    getrt(1, 1);
    dep[rt] = -1;
    dfs(rt, rt);
    printf("%d\n", ans);
    return 0;
}

换根dp：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
const int inf = 0x3f3f3f3f;
vector<int> g[N];
int n, dep[N], size[N], dp[N];
void dfs(int u, int p){
    if (u == p) dep[u] = 0;
    else dep[u] = dep[p]+1;
    size[u] = 1;
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if (v == p) continue;
        dfs(v, u);
        size[u] += size[v];
    }
}
void dfs1(int u, int p){
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if (v == p) continue;
        dp[v] = dp[u]-size[v]+(n-size[v]);
        dfs1(v, u);
    }
}
int main(void){
    scanf("%d", &n);
    for (int i = 0; i < n-1; ++i){
        int u, v; scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 1);
    for (int i = 1; i <= n; ++i) dp[1] += dep[i];
    dfs1(1, 1);
    int ans = inf;
    for (int i = 1; i <= n; ++i) ans = min(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}