1.什么是树的重心？
Ⅰ.找到一个节点，使得在该节点被删除后，分裂出来的所有连通块中，最大的那个连通块的大小（节点数）最小。（换句话说，重心是这棵树最“平衡”的一个点。）
Ⅱ.以该节点为根节点时，所有的子树(连通块)的大小不超过 N / 2
Ⅲ.树中所有其他节点距离之和最小的节点。
2.为什么要这么定义树的重心？
Ⅰ为了保证树上分治、二分、归并等操作复杂度最优，每次操作都找到树中最“平衡”的点开始，即树的重心。
Ⅱ树的重心到其他节点总距离最小。
3.怎么理解在定义中，Ⅰ和Ⅲ等价？
如果连通块不是最小，那么目前的节点可以朝着大的连通块方向”移动“一步，从而缩小总距离。
dfs求树的重心：
#include<bits/stdc++.h>
#define maxn = 1e5+4
#define inf 1e9+1
using namespace std;vector<int> adj[maxn];
int centroid; // 重心位置
int maxpart[maxn]; // 节点i作为分割点时最大连通块大小
int finalmaxpart = inf;
int sz[maxn]; // 以i为根的子树的大小
int n;void dfs(int u, int fa) {sz[u] = 1;maxpart[u] = 0;for (auto v : adj[u]) {if (v == p) continue;dfs(u, v);sz[u] += sz[v];maxpart[u] = max(maxpart[u], sz[v]);}if (maxpart[u] < finalmaxpart) {finalmaxpart = maxpart[u];centroid = u;}
}// dfs(rt, -1);