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