题目

题目描述：
牛妹有一张连通图，由n个点和n-1条边构成，也就是说这是一棵树，牛妹可以任意选一个点作为根，根的深度deproot为0。
对于任意一个非根的点，我们将他到根节点路径上的第一个点称作他的父节点，例如1为根。
1-4的：路径为1-3-5-4时，4的父节点是5，并且满足对任意非根节点，深度=父节点的深度+1。
整棵树的价值为所有结点的深度值之和。
牛妹希望这棵树的W最小，请你告诉她，选择哪个点可以使W最小。

输入描述：
第一行，一个数n。
接下来n-1行，每行两个数x,y，代表x-y是树上的一条边。

输出描述：
一行，一个数，最小的W。

解析一：树形dp（换根）

第一次写这种题目，所以在参考了邓老师的提示下，我总结一下~
  1. 首先正常操作，我们先用树的孩子表示法存储好树。
  2. 接下来我们应该求出每一个节点作为根时的权和。
  3. 最后我们选择最小的那个权和进行输出就行了。
这里我们呢要选择用dp以降低时间复杂度：
树形dp（换根）法：
  1. 这道题要我选一个点使深度和最小。
  2. 首先我们简单的dfs或bfs都会，但是暴力肯定不行，会超时的。
  3. 所以我们的目标就是用某一个根节点，推出当ta的子节点作为根时的权和。
  4. 那我们应该怎么推呢，我们能发现，如果是根节点的子结点当根节点时：该子结点的分支（包括自己）深度都会减一；而其他节点深度都会加一。
  5. 按照这个说法我们就能得到递推公式：F[y]=F[x]−cnt[y]+(n−cnt[y])。（我们假设F为某节点为根节点时的权和，cnt为某节点分支的节点数量，n为总节点数量）

换根图解

AC代码：树形dp（换根） 

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MAX = 1e6 + 7;
vector<int> Node[MAX];//树的孩子表示法
int F[MAX], depth[MAX], cnt[MAX];//F[i]表示当i为根时的权和；depth表示每个结点的深度；cnt表示每个结点的子树大小

void dfs(int x, int fa);//初始化depth数组和cnt数组
void dp(int x, int fa, int n);//换根dp求解每个结点的权和（F）

int main() {
    js;
    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        Node[u].push_back(v);
        Node[v].push_back(u);
    }
    //树的孩子表示法初始化
    dfs(1, -1);
    F[1] = 0;
    for (int i = 1; i <= n; i++)
        F[1] += depth[i];
    dp(1, -1, n);
    //求出各结点权和
    int min = 1;
    for (int i = 2; i <= n; i++)
        if (F[min] > F[i])
            min = i;
    //求出最大权和
    cout << F[min] << endl;
    return 0;
}

void dfs(int x, int fa) {
    //x为当前节点，fa为父节点
    if (fa == -1) depth[x] = 0;
    else depth[x] = depth[fa] + 1;
    cnt[x] = 1;
    for (auto c : Node[x])
        if (c != fa) {
            dfs(c, x);
            cnt[x] += cnt[c];
        }
}
void dp(int x, int fa, int n) {
    if (fa != -1) F[x] = F[fa] - cnt[x] + (n - cnt[x]);
    for (auto c : Node[x])
        if (c != fa)
            dp(c, x, n);
}

解析二：重心查找

这个嘛，我感觉也还有点小兰。
简单来说，就是找出我们要的那个那个根节点，然后再dfs或bfs一遍求出权和。
所以我们这里要用到一个性质：
  • 树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。
然后我们怎么用呢？这是关键
  1. 因为我们要距离和最小，我们同时也可以认为，就是这棵树最矮！
  2. 所以我们要选出可以让这颗树最矮的节点。
  3. 这里我们用到计算子树结点数的方法：我们需要进行一些操作，使得根节点的左子树和右子树的高度差最小。
那我们就开始操作！
  1. 我们先选取某一个节点为根节点，并用一个标记（pos）记住我们要的节点
  2. 我们先将pos放在叶节点上，然后按照中序遍历对每个节点进行计算。
  3. 与此同时，我们也正在计算每个节点的分支节点数（cnt）。（这里是同步进行的。为了方便理解计算过程，我们也可以直接认为我们已知每个点的分支节点数。）
  4. 我们先选取出我们正在操作的节点中，cnt最大的分支。（根节点的左右两边应该是不相上下的，所以我们先选最大）
  5. 然后再和我们已知的pos节点进行比较，保留较小者。（因为最大最小进行折中：就是最大里面的最小。所以就能得到一个折中值了）
ps：这里我觉得难理解的就是最大再最小的操作了，我也是理解学习了大佬的。
（所以我们可以这样想，总会有一个节点左右两边差不多。所有点的分支最大值一定是超过一半的，再从这些最大值里面选最小的，当然就正好是一半的那个啦）

AC代码：重心查找 

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MAX = 1e6 + 7;
vector<int> Node[MAX];//树的孩子表示法
int depth[MAX], cnt[MAX], son[MAX];//F[i]表示当i为根时的权和；depth表示每个结点的深度；cnt表示每个结点的子树大小；son表示子树的大小，最终是超过一半的最小数量
int pos = 0, ans = 0;//重心位置

void find(int x, int fa, int n);//查找重心
void dfs(int x, int fa);//初始化depth数组和cnt数组

int main() {
    js;
    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        Node[u].push_back(v);
        Node[v].push_back(u);
    }
    //树的孩子表示法初始化
    find(1, -1, n);
    dfs(pos, -1);
    cout << ans << endl;
    return 0;
}

void find(int x, int fa, int n) {
    cnt[x] = 1; son[x] = 0;
    for (auto c : Node[x])
        if (c != fa) {
            find(c, x, n);
            cnt[x] += cnt[c];
            son[x] = max(son[x], cnt[c]);
        }
    son[x] = max(son[x], n - cnt[x]);
    if (!pos) pos = x;
    else if (son[x] < son[pos]) pos = x;
}
void dfs(int x, int fa) {
    //x为当前节点，fa为父节点
    if (fa == -1) depth[x] = 0;
    else depth[x] = depth[fa] + 1;
    ans += depth[x];
    for (auto c : Node[x])
        if (c != fa)
            dfs(c, x);
}