为什么这个题会有图论的标签啊，虽然图论也包括找树的重心，可是这很容易让人联想到最短路，但不得不说，这是一个典型的找树的重心模板题。
树的重心是什么？
找到一个点,其所有的子树中最大的子树节点数最少,则这个点便是树的重心。
而我们找树的重心该怎么找呢，我们可以从定义入手，我们可以搜索。
我们先设任意一个点为树的根（比如 1 号节点），这样就把这棵树变成了有根树。
然后我们可以求出每个节点的总子树大小和最大子树大小，然后可以得到递推式。
我们可以初始化每个节点的size都为1.
size[i] = size[i] + size[j] (j是i的子树)
然后就可以愉快地上代码了
#include#include #include #include using namespace std;struct cym { int from, to, next;}e[1000100];int cnt, lin[1000100], dp[1000100], size[1000100], n, vis[1000010];inline void add(int f, int t){ e[++cnt].from = f; e[cnt].to = t; e[cnt].next = lin[f]; lin[f] = cnt;}inline void dfs (int now, int fa){ vis[now] = 1; for(int i = lin[now]; i; i = e[i].next) { if(e[i].to == fa) continue; if(!vis[e[i].to]) { dfs(e[i].to, now); size[now] += size[e[i].to] + 1; dp[now] = max(dp[now], size[e[i].to] + 1); } } dp[now] = max(dp[now], n - size[now] - 1); vis[now] = 0;}//inline int dfs2(int now, int fa)//{// //}int main(){ scanf("%d", &n); for(int i = 1; i <= n - 1; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b); add(b, a); } dfs(1, 0); dp[0] = 21474836;int k = 0; for(int i = 1; i <= n; i++) if(dp[k] > dp[i]) k = i; printf("%d ", k); memset(size, 0, sizeof(size)); dfs(k, 0); int ans = 0; for(int i = 1; i <= n; i++) ans += size[i]; printf("%d", ans); return 0;}