POJ 1655 Balancing Act[树的重心]
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define N 20010
int s[N], f[N], n, root;
vector<int> g[N];
void getroot(int now, int fa) {
int u;
s[now] = 1;
f[now] = 0;
for (int i=0; i<g[now].size(); i++)
if ((u=g[now][i]) != fa) {
getroot(u, now);
s[now] += s[u];
f[now] = max(f[now], s[u]);
}
f[now] = max(f[now], n-s[now]);
if (f[now] < f[root]) root = now;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int T, a, b;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i=1; i<=n; i++) g[i].clear();
for (int i=1; i<n; i++) {
scanf("%d%d", &a, &b);
g[a].push_back(b); g[b].push_back(a);
}
f[0] = n;
getroot(1, root=0);
int cnt = 0;
for (int i=1; i<=n; i++) if (f[i] == f[root]) {
root = i; break;
}
printf("%d %d\n", root, f[root]);
}
return 0;
}
补充：软件开发 , C++ ,
