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

Solution (Python):
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)

Solution (Python):
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):
    
    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)

Solution (Python):
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):
    
    
    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):
    
    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)