C++

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

 

using namespace std;

int N;

vector<int> vec[10010];

 

int calc_cnt(int v, int p)

{

    int cnt = 0;

    for(auto c : vec[v])

    {

        if(c == p)

            continue;

        cnt += calc_cnt(c, v);

    }

 

    if(p == 0)

        cnt += (vec[v].size() + 1) / 2;

    else

        cnt += (vec[v].size() - 1) / 2;

    return cnt;

}

 

int check_len(int idx, const vector<int>& len_vec, int m)

{

    int s=0,e=len_vec.size()-1;

    while(s<e){

        if(s==idx)

            s++;

        if(e==idx)

            e--;

        if(len_vec[s]+len_vec[e]>m)

            return 0;

        s++, e--;

    }

    return 1;

}

 

int serch(int v,int p, int m){

    vector<int> len_vec;

    for(auto c : vec[v])

    {

        if(c == p)

            continue;

        int len = serch(c, v, m);

        if(len == -1)

            return -1;

        len_vec.push_back(len + 1);

    }

 

    if(p && len_vec.size() % 2 == 0)

        len_vec.push_back(0);

 

    sort(len_vec.begin(), len_vec.end());

 

    if(p == 0)

    {

        if(len_vec.size() % 2)

        {

            if(len_vec.back() > m)

                return - 1;

            len_vec.pop_back();

        }

 

        for(int s = 0, e = len_vec.size()-1; s < e; s++, e--)

        {

            if(len_vec[s]+len_vec[e]>m)

                return -1;

        }

        return 0;

    }

 

    int lb = 0, ub = len_vec.size();

    while(lb < ub)

    {

        int idx = (lb + ub) / 2;

        if(check_len(idx, len_vec, m))

            ub = idx;

        else

            lb = idx + 1;

    }

 

    if(ub == (int)len_vec.size())

        return -1;

    return len_vec[ub] > m ? -1 : len_vec[ub];

}

 

int main()

{

   scanf("%d",&N);

   for(int i=1;i<=N-1;i++){

        int a,b;

        scanf("%d %d",&a,&b);

        vec[a].push_back(b);

        vec[b].push_back(a);

   }

 

   printf("%d ",calc_cnt(1, 0));

 

   int lb = 1, ub = N - 1;

   while(lb < ub)

   {

       int m = (lb + ub) / 2;

       if(serch(1, 0, m) == -1)

            lb = m + 1;

       else

            ub = m;

   }

   printf("%d", ub);

    return 0;

}