树的重心的定义是： 一个点的所有子树中节点数最大的子树节点数最小。
这句话可能说起来比较绕，但是其实想想他的字面意思也就是找到最平衡的那个点。
题目大意： 直接给你一棵树，让你求树的重心，如果有多个，找出编号最小的那个，并输出他的子树当中最大的节点数。
思路：利用dfs求出每个点的所有孩子数目，然后在dfs一下求出树的重心。
用途：树的重心在树分治的点分治中有重要作用。具体可以看上篇树分治的题目http://www.cnblogs.com/Howe-Young/p/4776852.html
代码：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 42000; const int inf = 0x3f3f3f3f; int tot, head[maxn]; struct Edge { int to, next; }edge[maxn]; int siz[maxn]; void init() { tot = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } int dfs_size(int u, int fa) { siz[u] = 1; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa) continue; siz[u] += dfs_size(v, u); } return siz[u]; } int minn; void dfs_balance(int u, int fa, int totnum, int &root) { int maxx = totnum - siz[u]; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa) continue; dfs_balance(v, u, totnum, root); maxx = max(maxx, siz[v]); } if (maxx < minn || maxx == minn && root > u) { minn = maxx; root = u; } } void solve() { int totnum = dfs_size(1, 0); minn = inf; int root; dfs_balance(1, 0, totnum, root); printf("%d %d ", root, minn); } int main() { int T, n; scanf("%d", &T); while (T--) { init(); scanf("%d", &n); int u, v; for (int i = 1; i < n; i++) { scanf("%d %d", &u, &v); addedge(u, v); addedge(v, u); } solve(); } return 0; }
POJ 3107
题目大意： 还是给出一棵树，让求它的所有的重心。
思路：基本上和上一个题目一样，就是多了所有的重心。在求所有的重心的时候如果找到了最小的比之前的都小，那么现在就它一个，如果相等的话，就继续往上加，因为还没找到比他还小的
代码：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 110000; const int inf = 0x3f3f3f3f; int tot, head[maxn]; struct Edge { int to, next; }edge[maxn]; int siz[maxn]; int res[maxn], index; void init() { tot = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } int dfs_size(int u, int fa) { siz[u] = 1; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa) continue; siz[u] += dfs_size(v, u); } return siz[u]; } int minn; void dfs_balance(int u, int fa, int totnum) { int maxx = totnum - siz[u]; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa) continue; dfs_balance(v, u, totnum); maxx = max(maxx, siz[v]); } if (maxx < minn) { minn = maxx; index = 0; res[index++] = u; } else if (maxx == minn) { res[index++] = u; } } void solve() { int totnum = dfs_size(1, 0); minn = inf; dfs_balance(1, 0, totnum); sort(res, res + index); for (int i = 0; i < index; i++) printf("%d ", res[i]); puts(""); } int main() { int n; while (~scanf("%d", &n)) { init(); int u, v; for (int i = 1; i < n; i++) { scanf("%d %d", &u, &v); addedge(u, v); addedge(v, u); } solve(); } return 0; }