# 【題解】TIOJ 1947 . 小向的試煉 1-3：森林(Forest)

【題目敘述】https://tioj.ck.tp.edu.tw/problems/1947
【解題想法】subtree size, 樹重心

```#include <iostream>
#include <vector>
using namespace std;

int n, a, b, sz[1000005], mn = 1000006;
vector <int> v[1000005];

void f(int now, int pre){
sz[now] = 1;
int mx = 0;
for (int i:v[now]){
if (i == pre) continue;
f(i, now);
sz[now] += sz[i];
mx = max(mx, sz[i]);
}
mx = max(mx, n-sz[now]);
mn = min(mn, mx);

return;
}

int main() {
cin >> n;
for (int i = 1; i < n; i++){
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
f(0, -1);
cout << mn << "\n";
}
```
```#include <iostream>
#include <vector>
using namespace std;

int n, a, b, sz[1000005];
vector <int> v[1000005];

void f(int now, int pre){
sz[now] = 1;
for (int i:v[now]){
if (i == pre) continue;
f(i, now);
sz[now] += sz[i];
}
return;
}

int main() {
cin >> n;
for (int i = 1; i < n; i++){
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
f(0, -1);
int now = 0;
while (1){
int nx = -1;
for (int i:v[now]){
if (sz[i] > sz[now]) continue;
if (sz[i] * 2 > n){
nx = i;
break;
}
}
if (nx != -1) now = nx;
else break;
}
int mx = 0;
for (int i:v[now]){
if (sz[i] > sz[now]) continue;
mx = max(mx, sz[i]);
}
mx = max(mx, n-sz[now]);
cout << mx << "\n";
}
```