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

#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";
}