Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

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
    U = sorted(x for x in A if x > half)
    D = sorted([x for x in A if x <= half], reverse=True)
    cand = []
    rest_U = []
    complete = 0
    while U and U[-1] == S:
        U.pop()
        complete += 1
    for y in U[::-1]:
        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)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

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
    U = sorted(x for x in A if x > half)
    D = deque(sorted(x for x in A if x <= half))
    cand = []
    rest_U = []
    complete = 0
    while U and U[-1] == S:
        U.pop()
        complete += 1
    for y in U[::-1]:
        while D and D[0] + y <= S:
            cand.append(D.popleft())
        if cand:
            cand.pop()
            complete += 1
        else:
            rest_U.append(y)
    cand += D
    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)

Fixed submission:
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)