Submission #2213226

---

Source Code Expand

#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
#define vv(a,b,c,d) vector<vector<a> >(b,vector<a>(c,d))
#define vvv(a,b,c,d,e) vector<vector<vector<a> > >(b,vv(a,c,d,e))
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

const int INF = 100005;
int N;
vi G[100005];
vi va[100005];

int bin(vi &a, int r, int lim) {
    auto g = [&](int mid) {
        int i = 0, j = r - 1;
        for (int k = 0; k < r / 2;) {
            if (i == mid) i++;
            else if (j == mid)j--;
            else {
                k++;
                if (a[i++] + a[j--] > lim) {
                    RT 0;
                }
            }
        }
        RT 1;
    };

    if (!g(r - 1))RT - 1;

    int ok = r - 1, ng = -1;
    while (ok - ng > 1) {
        int mid = (ok + ng) / 2;
        (g(mid) ? ok : ng) = mid;
    }
    RT ok;
}

int f(int u, int p, int lim) {
    int C = sz(G[u]) - 1;

    auto &a = va[u];
    if (sz(a) < C) {
        a.reserve(C);
        a.resize(C);
    }

    for (int i = 0, j = 0; i < sz(G[u]); ++i) {
        int v = G[u][i];
        if (v != p) {
            a[j++] = f(v, u, lim);
        }
    }
    sort(all(a));
    if (sz(a) && a.back() > lim)RT INF;

    if (C % 2) {
        rep(i, C / 2) if (a[i] + a[C - 2 - i] > lim)RT INF;
        int k = bin(a, C, lim);
        if (k == -1)RT INF;
        RT a[k] + 1;
    } else {
        int chk = 1;
        rep(i, C / 2) {
            if (a[i] + a[C - 1 - i] > lim) {
                chk = 0;
                break;
            }
        }
        if (chk)RT 1;

        int k = bin(a, C - 1, lim);
        if (k == -1)RT INF;
        RT a[k] + 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    cin >> N;
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int A = 0;
    rep(i, N + 1)A += sz(G[i]) & 1;
    A /= 2;
    G[1].push_back(0);

    int ng = 0, ok = N;
    while (ok - ng > 1) {
        int mid = (ng + ok) / 2;
        int re = f(1, 0, mid);
        (re - 1 <= mid ? ok : ng) = mid;
    }
    
    int B = ok;
    cout << A << ' ' << B << endl;
    f(1, 0, 4);
}

Submission Info

Judge Result