Problem:


Score : 900 points

Problem Statement

Takahashi has decided to make a Christmas Tree for the Christmas party in AtCoder, Inc.

A Christmas Tree is a tree with N vertices numbered 1 through N and N-1 edges, whose i-th edge (1\leq i\leq N-1) connects Vertex a_i and b_i.

He would like to make one as follows:

Specify two non-negative integers A and B.

Prepare A Christmas Paths whose lengths are at most B. Here, a Christmas Path of length X is a graph with X+1 vertices and X edges such that, if we properly number the vertices 1 through X+1, the i-th edge (1\leq i\leq X) will connect Vertex i and i+1.

Repeat the following operation until he has one connected tree:

Select two vertices x and y that belong to different connected components. Combine x and y into one vertex. More precisely, for each edge (p,y) incident to the vertex y, add the edge (p,x). Then, delete the vertex y and all the edges incident to y.

Properly number the vertices in the tree.

Takahashi would like to find the lexicographically smallest pair (A,B) such that he can make a Christmas Tree, that is, find the smallest A, and find the smallest B under the condition that A is minimized.

Solve this problem for him.

Constraints

2 \leq N \leq 10^5

1 \leq a_i,b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

For the lexicographically smallest (A,B), print A and B with a space in between.

Sample Input 1

7
1 2
2 3
2 4
4 5
4 6
6 7

Sample Output 1

3 2

We can make a Christmas Tree as shown in the figure below:

Sample Input 2

8
1 2
2 3
3 4
4 5
5 6
5 7
5 8

Sample Output 2

2 5

Sample Input 3

10
1 2
2 3
3 4
2 5
6 5
6 7
7 8
5 9
10 5

Sample Output 3

3 4



Sample input:
7
1 2
2 3
2 4
4 5
4 6
6 7


Sample output:
3 2

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(i, mx, len_odd):
        if i == len_odd:
            return mx
        if fin[i]:
            return dfs(i + 1, mx, len_odd)
        res = inf
        fin[i] = True
        u = odd_degree_nodes[i]
        for j in range(i + 1, len_odd):
            if fin[j]: continue
            fin[j] = True
            v = odd_degree_nodes[j]
            res = min(res, dfs(i + 1, max(mx, dist[u][v]), len_odd))
            fin[j] = False
        fin[i] = False
        return res

    inf = 10 ** 6
    n = int(input())
    to = defaultdict(list)
    for _ in range(n - 1):
        a, b = map(int1, input().split())
        to[a].append(b)
        to[b].append(a)
    odd_degree_nodes = []
    for u in range(n):
        if len(to[u]) % 2:
            odd_degree_nodes.append(u)
    # print(odd_degree_nodes)
    ans_a = len(odd_degree_nodes) // 2

    dist = [[inf] * n for _ in range(n)]
    for u in range(n):
        dist[u][u] = 0
        for v in to[u]:
            dist[u][v] = dist[v][u] = 1
    for w in range(n):
        for u in range(n):
            for v in range(n):
                new_dist = dist[w][u] + dist[w][v]
                if new_dist < dist[u][v]:
                    dist[u][v] = dist[v][u] = new_dist
    # p2D(dist)

    fin = [False] * len(odd_degree_nodes)
    ans_b = dfs(0, 0, len(odd_degree_nodes))
    print(ans_a, ans_b)

main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

input=sys.stdin.readline

N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

parent=[-1]*N
parent[0]=0
que=deque([0])
ans=[0]
while que:
    v=que.popleft()
    for nv in edge[v]:
        if parent[nv]==-1:
            parent[nv]=v
            que.append(nv)
            ans.append(nv)

ans=ans[::-1]

def cond(n):
    dp=[-1]*N
    for v in ans:
        if v!=0:
            temp=[]
            if len(edge[v])==1:
                dp[v]=1
            else:
                for nv in edge[v]:
                    if nv!=parent[v]:
                        r=dp[nv]
                        if r==-1:
                            return False
                        temp.append(r)
                if len(temp)%2==0:
                    temp.append(0)
                temp.sort()
                start=0
                end=len(temp)-1
                while end-start>1:
                    test=(end+start)//2
                    check=True
                    s=0;t=len(temp)-1
                    while t>s:
                        if s==test:
                            s+=1
                        elif t==test:
                            t-=1
                        else:
                            if temp[s]+temp[t]>n:
                                check=False
                            s+=1
                            t-=1
                    if check:
                        end=test
                    else:
                        start=test
                check=True
                s=0;t=len(temp)-1
                while t>s:
                    if s==start:
                        s+=1
                    elif t==start:
                        t-=1
                    else:
                        if temp[s]+temp[t]>n:
                            check=False
                        s+=1
                        t-=1
                if check:
                    dp[v]=temp[start]+1
                else:
                    check=True
                    s=0;t=len(temp)-1
                    while t>s:
                        if s==end:
                            s+=1
                        elif t==end:
                            t-=1
                        else:
                            if temp[s]+temp[t]>n:
                                check=False
                            s+=1
                            t-=1
                    if check:
                        dp[v]=temp[end]+1
                    else:
                        return False
        else:
            temp=[]
            for nv in edge[v]:
                temp.append(dp[nv])
            if len(temp)%2==1:
                temp.append(0)
            temp.sort()
            k=len(temp)//2
            for i in range(k):
                test=temp[i]+temp[-i-1]
                if test>n:
                    return False
            return True

A=(len(edge[0])+1)//2
for i in range(1,N):
    A+=(len(edge[i])-1)//2

start=0
end=N-1
while end-start>1:
    test=(end+start)//2
    if cond(test):
        end=test
    else:
        start=test

print(A,end)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_right

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

def make_pairs(A,S):
    half = S//2
    A.sort()
    complete = 0
    while A and A[-1] == S:
        A.pop()
        complete += 1
    i = bisect_right(A,half)
    U = A[i:][::-1]
    D = A[:i][::-1]
    cand = []
    rest_U = []
    for y in U:
        while D and D[-1] + y <= S:
            cand.append(D.pop())
        if cand:
            cand.pop()
            complete += 1
        else:
            rest_U.append(y)
    cand += D[::-1]
    L = len(cand)
    if L & 1:
        # 一番小さいものを余らせる
        complete += L // 2 + len(rest_U)
        return complete, cand[0]
    else:
        complete += L // 2
        if rest_U:
            return complete + len(rest_U) - 1, rest_U[-1]
        else:
            return complete, 0

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

def num_of_seg(B):
    # 長さBまで許容したとき、いくつの線分が必要になるか
    dp = [0] * (N+1)
    seg_lens = [[] for _ in range(N+1)]
    for v in order[::-1]:
        p = parent[v]
        A = seg_lens[v]
        pair, r = make_pairs(A,B)
        dp[v] += pair
        if v == root:
            if r:
                return dp[v] + 1
            else:
                return dp[v]
        dp[p] += dp[v]
        seg_lens[p].append(r + 1)

opt_A = num_of_seg(N+10)
left = 0 # むり
right = N + 10 # 可能
while left + 1 < right:
    x = (left + right) // 2
    if num_of_seg(x) == opt_A:
        right = x
    else:
        left = x
B = right
A = opt_A
print(A,B)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_left, bisect_right

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

def make_pairs(S,x):
    # a + b <= x となるペアをなるべくたくさん作る
    # nペア（なるべくたくさん）作ったあと、1つ短い長さが残る
    seg = 0
    while S and S[-1] == x:
        S.pop()
        seg += 1
    i = bisect_right(S,x//2)
    lower = S[:i][::-1]; upper = S[i:]
    cand = []
    rest = []
    for b in upper[::-1]:
        while lower and lower[-1] + b <= x:
            cand.append(lower.pop())
        if cand:
            cand.pop()
            seg += 1
        else:
            rest.append(b)
    cand += lower[::-1]
    L = len(cand)
    q,r = divmod(L,2)
    if r:
        return seg + len(rest) + q, cand[0]
    else:
        seg += q
        if rest:
            return seg + len(rest) - 1, rest[-1]
        else:
            # 全部ペアになった
            return seg, 0

def solve(x):
    # 長さ x までの線分を許容した場合に、必要となる本数を返す
    dp = [0] * (N+1)
    temp = [[] for _ in range(N+1)] # 下から出てくる長さ
    for v in order[::-1]:
        p = parent[v]
        S = temp[v]
        S.sort()
        s, l = make_pairs(S,x)
        dp[v] += s        
        dp[p] += dp[v]
        temp[p].append(l + 1)
        if v == 1:
            return dp[1] if not l else dp[1] + 1

seg = solve(N + 10)
left = 0 # むり
right = N # できる
while left + 1 < right:
    x = (left + right) // 2
    if solve(x) == seg:
        right = x
    else:
        left = x
print(seg, right)

Submission status: Runtime Error

Solution code:
import sys,heapq

input=sys.stdin.readline

N=int(input())
edge=[[] for i in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,pv,n):
    #print(v,pv,len(edge[v]))
    if v!=0:
        if len(edge[v])==1:
            return 1
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return -1
                temp.append(r)
        if len(temp)%2==0:
            temp.append(0)
        elif len(temp)==1:
            return temp[0]+1
        temp.sort()
        que=[]
        #ban=set([])
        k=len(temp)//2
        for i in range(k):
            heapq.heappush(que,(-temp[i+1]-temp[-i-1],i+1,N-1-i))
        for i in range(k):
            val,id1,id2=heapq.heappop(que)
            while id1+id2==N and id1<=i:
                val,id1,id2=heapq.heappop(que)
            if val>=-n:
                return temp[i]+1
            heapq.heappush(que,(-temp[i]-temp[-i-1],i,N-1-i))
            #ban.add((i+1,N-1-i))
        for i in range(k):
            val,id1,id2=heapq.heappop(que)
            while (id1+id2==N) or (id1+id2==N-1 and id2<i+k):
                val,id1,id2=heapq.heappop(que)
            if val>=-n:
                return temp[i+k]+1
            heapq.heappush(que,(-temp[k-1-i]-temp[i+k],k-1-i,i+k))
            #ban.add((N-1-i-k,i+k))
        val,id1,id2=heapq.heappop(que)
        while id1+id2!=2*k-1:
            val,id1,id2=heapq.heappop(que)
        if val>=-n:
            return temp[-1]+1

        return -1
    else:
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return False
                temp.append(r)
        if len(temp)%2==1:
            temp.append(0)
        temp.sort()
        k=len(temp)//2
        for i in range(k):
            test=temp[i]+temp[-i-1]
            if test>n:
                return False
        return True

A=(len(edge[0])+1)//2
for i in range(1,N):
    A+=(len(edge[i])-1)//2

start=0
end=N-1
while end-start>1:
    t=(end+start)//2
    if dfs(0,-1,t):
        end=t
    else:
        start=t

print(A,end)


#ans=dfs(0,-1)
#print("YES" if ans else "NO")

Submission status: Runtime Error

Solution code:
import sys,heapq

input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)

N=int(input())
edge=[[] for i in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,pv,n):
    #print(v,pv,len(edge[v]))
    if v!=0:
        if len(edge[v])==1:
            return 1
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return -1
                temp.append(r)
        if len(temp)%2==0:
            temp.append(0)
        elif len(temp)==1:
            return temp[0]+1
        temp.sort()
        que=[]
        #ban=set([])
        k=len(temp)//2
        for i in range(k):
            heapq.heappush(que,(-temp[i+1]-temp[-i-1],i+1,N-1-i))
        for i in range(k):
            val,id1,id2=heapq.heappop(que)
            while id1+id2==N and id1=<i:
                val,id1,id2=heapq.heappop(que)
            if val>=-n:
                return temp[i]+1
            heapq.heappush(que,(-temp[i]-temp[-i-1],i,N-1-i))
            #ban.add((i+1,N-1-i))
        for i in range(k):
            val,id1,id2=heapq.heappop(que)
            while (id1+id2==N) or (id1+id2==N-1 and id2<i+k):
                val,id1,id2=heapq.heappop(que)
            if val>=-n:
                return temp[i+k]+1
            heapq.heappush(que,(-temp[k-1-i]-temp[i+k],k-1-i,i+k))
            #ban.add((N-1-i-k,i+k))
        val,id1,id2=heapq.heappop(que)
        while id1+id2!=2*k-1:
            val,id1,id2=heapq.heappop(que)
        if val>=-n:
            return temp[-1]+1

        return -1
    else:
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return False
                temp.append(r)
        if len(temp)%2==1:
            temp.append(0)
        temp.sort()
        k=len(temp)//2
        for i in range(k):
            test=temp[i]+temp[-i-1]
            if test>n:
                return False
        return True

A=(len(edge[0])+1)//2
for i in range(1,N):
    A+=(len(edge[i])-1)//2

start=0
end=N-1
while end-start>1:
    t=(end+start)//2
    if dfs(0,-1,t):
        end=t
    else:
        start=t

print(A,end)

Submission status: Runtime Error

Solution code:
import sys,heapq

input=sys.stdin.readline

N=int(input())
edge=[[] for i in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,pv,n):
    #print(v,pv,len(edge[v]))
    if v!=0:
        if len(edge[v])==1:
            return 1
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return -1
                temp.append(r)
        check=True
        if len(temp)%2==0:
            temp.append(0)
            check=False
        elif len(temp)==1:
            return temp[0]+1
        temp.sort()
        que=[]
        ban=set([])
        k=len(temp)//2
        for i in range(k):
            heapq.heappush(que,(-temp[i+1]-temp[-i-1],i+1,N-1-i))
        for i in range(k):
            if i==0:
                if check:
                    val,id1,id2=heapq.heappop(que)
                    while (id1,id2) in ban:
                        val,id1,id2=heapq.heappop(que)
                    if val>=-n:
                        return temp[i]+1
                heapq.heappush(que,(-temp[i]-temp[-i-1],i,N-i-1))
                ban.add((i+1,N-1-i))
            else:
                val,id1,id2=heapq.heappop(que)
                while (id1,id2) in ban:
                    val,id1,id2=heapq.heappop(que)
                if val>=-n:
                    return temp[i]+1
                heapq.heappush(que,(-temp[i]-temp[-i-1],i,N-1-i))
                ban.add((i+1,N-1-i))
        for i in range(k):
            val,id1,id2=heapq.heappop(que)
            while (id1,id2) in ban:
                val,id1,id2=heapq.heappop(que)
            if val>=-n:
                return temp[i+k]+1
            heapq.heappush(que,(-temp[k-1-i]-temp[i+k],k-1-i,i+k))
            ban.add((N-1-i-k,i+k))
        val,id1,id2=heapq.heappop(que)
        while (id1,id2) in ban:
            val,id1,id2=heapq.heappop(que)
        if val>=-n:
            return temp[-1]+1

        return -1
    else:
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return False
                temp.append(r)
        if len(temp)%2==1:
            temp.append(0)
        temp.sort()
        k=len(temp)//2
        for i in range(k):
            test=temp[i]+temp[-i-1]
            if test>n:
                return False
        return True

A=(len(edge[0])+1)//2
for i in range(1,N):
    A+=(len(edge[i])-1)//2

start=0
end=N-1
while end-start>1:
    t=(end+start)//2
    if dfs(0,-1,t):
        end=t
    else:
        start=t

print(A,end)

Submission status: Runtime Error

Solution code:
n = int(input())
edge = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

cnt = [1] *(n+1)

a = 0
for i in range(1, n+1):
    if len(edge[i]) % 2 == 1:
        a += 1

a //= 2

def init_dfs(x, last = -1):
    for to in edge[x]:
        if to == last:continue
        init_dfs(to, x)
        cnt[x] += cnt[to]

init_dfs(1)

def check(tmp, b):
    k = len(tmp)
    if k == 1:
        return True, tmp[0]
    for i in range(k//2):
        if tmp[i] + tmp[k-2-i] > b:
            return False, 0
    for i in range(k // 2):
        if tmp[i] + tmp[k-1-i] > b:
            return True, tmp[k-1-i]
    for i in range(k // 2 + 1, 0, -1):
        if tmp[i] + tmp[k-i] > b:
            return True, tmp[i]
    return True, tmp[0]
                            
        

def dfs(x, b, last = -1):
    tmp = []
    for to in edge[x]:
        if to == last:continue
        ok, length = dfs(to, b, x)
        if not ok:return False, 0
        if length == b:return False, 0
        tmp.append(length + 1)
    tmp.sort()
    k = len(tmp)
    if k % 2 == 0:
        ok = True
        for i in range(k//2):
            if tmp[i] + tmp[k-1-i] > b:
                ok = False
        if ok:
            return True, 0

        tmp.pop()
    return check(tmp, b)

bottom = 0
top = n

while top - bottom > 1:
    mid = (top + bottom) // 2
    if dfs(1, mid)[0]:
        top = mid
    else:
        bottom = mid
print(a, top)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
from math import log2

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def init(i, oi=-1, dpt=0):
        depth[i] = dpt
        parent_2k[0][i] = oi
        for ki in to[i]:
            if ki == oi: continue
            init(ki, i, dpt + 1)
        return

    def make_parent(level):
        parent_2kk1 = parent_2k[0]
        for k in range(1, level):
            parent_2kk = parent_2k[k]
            for i in range(n):
                parent1 = parent_2kk1[i]
                if parent1 != -1:
                    parent_2kk[i] = parent_2kk1[parent1]
            parent_2kk1 = parent_2kk
        return

    def lca(u, v):
        dist_uv = depth[u] - depth[v]
        if dist_uv < 0:
            u, v = v, u
            dist_uv *= -1

        k = 0
        while dist_uv:
            if dist_uv & 1:
                u = parent_2k[k][u]
            dist_uv >>= 1
            k += 1

        if u == v:
            return u

        for k in range(int(log2(depth[u])) + 1, -1, -1):
            pu = parent_2k[k][u]
            pv = parent_2k[k][v]
            if pu != pv:
                u = pu
                v = pv
        return parent_2k[0][u]

    def dfs(i, mx, len_odd):
        if i == len_odd:
            return mx
        if fin[i]:
            return dfs(i + 1, mx, len_odd)
        res = inf
        fin[i] = True
        for j in range(i + 1, len_odd):
            if fin[j]: continue
            fin[j] = True
            res = min(res, dfs(i + 1, max(mx, dist[i][j]), len_odd))
            fin[j] = False
        fin[i] = False
        return res

    inf = 10 ** 6
    n = int(input())
    to = defaultdict(list)
    for _ in range(n - 1):
        a, b = map(int1, input().split())
        to[a].append(b)
        to[b].append(a)
    depth = [0] * n
    level = int(log2(n)) + 1
    parent_2k = [[-1] * n for _ in range(level)]
    init(0)
    make_parent(level)

    odd_degree_nodes = []
    for u in range(n):
        if len(to[u]) % 2:
            odd_degree_nodes.append(u)
    # print(odd_degree_nodes)
    len_odd = len(odd_degree_nodes)
    ans_a = len_odd // 2

    dist = [[-1] * len_odd for _ in range(len_odd)]
    for j in range(len_odd):
        v = odd_degree_nodes[j]
        for i in range(j):
            u = odd_degree_nodes[i]
            lca_uv = lca(u, v)
            dist[i][j] = dist[j][i] = depth[u] + depth[v] - 2 * depth[lca_uv]
    # p2D(dist)

    fin = [False] * len_odd
    ans_b = dfs(0, 0, len_odd)
    print(ans_a, ans_b)

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import bisect

n = 0
edges = None
visited = None

def dfs(v, b, r = False):
    global visited

    if not r:
        visited = [False] * n

    visited[v] = True
    lengths = []
    for c in edges[v]:
        if not visited[c]:
            k = dfs(c, b, True)
            if k < 0 or b < k:
                return -1
            lengths.append(k)

    odd = (len(lengths) % 2 == 1) ^ r
    lengths.sort()
    while 1 < len(lengths):
        k = lengths.pop()
        i = bisect.bisect_right(lengths, b - k)
        if i == 0:
            if odd:
                odd = False
            else:
                return -1
        else:
            lengths.pop(i - 1)

    if len(lengths) == 0:
        return 1
    else:
        return lengths[0] + 1


def solve():

    root = None
    a = 1

    for i in range(n):
        c = len(edges[i])
        if 3 <= c:
            a += (c - 1) // 2
            root = i

    if root is None:
        return 1, n - 1

    ok = n - 1
    ng = 1

    while ng + 1 < ok:
        mid = (ok + ng) // 2
        if 0 <= dfs(root, mid):
            ok = mid
        else:
            ng = mid

    return a, ok


def main():
    global n
    global edges

    n = int(input())
    edges = [[] for _ in range(n)]
    for i in range(n - 1):
        a, b = input().split()
        a = int(a) - 1
        b = int(b) - 1
        edges[a].append(b)
        edges[b].append(a)

    a, b = solve()
    print('{} {}'.format(a, b))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import bisect

n = 0
edges = None
visited = None

def dfs(v, b, r = False):
    global visited

    if not r:
        visited = [False] * n
        count = [0] * n

    visited[v] = True
    lengths = []
    for c in edges[v]:
        if not visited[c]:
            k = dfs(c, b, True)
            if k < 0:
                return -1
            lengths.append(k)

    odd = (len(lengths) % 2 == 1) ^ r
    lengths.sort()
    while 1 < len(lengths):
        k = lengths.pop()
        if b < k:
            return -1
        elif k == b and odd:
            odd = False
        else:
            i = bisect.bisect_right(lengths, b - k)
            if i == 0:
                return -1
            lengths.pop(i - 1)
    if len(lengths) == 0:
        return 1
    else:
        return lengths[0] + 1


def solve():

    root = None
    a = 1

    for i in range(n):
        c = len(edges[i])
        if 3 <= c:
            a += (c - 1) // 2
            root = i

    if root is None:
        return 1, n - 1

    ok = n - 1
    ng = 1

    while ng + 1 < ok:
        mid = (ok + ng) // 2
        if 0 <= dfs(root, mid):
            ok = mid
        else:
            ng = mid

    return a, ok


def main():
    global n
    global edges

    n = int(input())
    edges = [[] for _ in range(n)]
    for i in range(n - 1):
        a, b = input().split()
        a = int(a) - 1
        b = int(b) - 1
        edges[a].append(b)
        edges[b].append(a)

    a, b = solve()
    print('{} {}'.format(a, b))


if __name__ == '__main__':
    main()