POJ - 1655 Balancing Act

求树的重心

树的重心也叫树的质心。对于一棵树n个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数最小。换句话说，删除这个点后最大连通块（一定是树）的结点数最小。

我们假设以 1 为根节点，那么我们只能求到任意一个点的子树的大小，并不知道这个点的父节点方向的联通分量的节点个数，但我们已知这个节点的子树大小，并且所有节点数目为 n ，那么我们可以知道这个点的父节点方向的联通分量的节点个数，然后每个点的子树的最大节点数就算出来了，然后遍历一次，就得到了树的重心。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
struct edge
{
	int to;
	int nex;
}e[MAXN * 2];
int head[MAXN], tot = 1;
void add(int a, int b)
{
	e[tot] = edge{ b,head[a] };
	head[a] = tot++;
}
int num[MAXN], dp[MAXN], n;
void init()
{
	memset(head, -1, sizeof(head));
	tot = 1;
	memset(num, 0, sizeof(num));
	memset(dp, 0, sizeof(dp));
}
void dfs(int u, int fa)
{
	num[u] = 1;
	for (int i = head[u]; i + 1; i = e[i].nex)
	{
		int v = e[i].to;
		if (v != fa)
		{
			dfs(v, u);
			dp[u] = max(dp[u], num[v]);
			num[u] += num[v];
		}
	}
	dp[u] = max(dp[u], n - num[u]);
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		init();
		int a, b;
		scanf("%d", &n);
		for (int i = 1; i < n; i++)
		{
			scanf("%d%d", &a, &b);
			add(a, b);
			add(b, a);
		}
		dfs(1, 0);
		int res = n, end = 0;
		for (int i = 1; i <= n; i++)
		{
			if (dp[i] < res)
			{
				res = dp[i];
				end = i;
			}
		}
		printf("%d %d\n", end, res);
	}
}