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: Wrong Answer

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)
                temp.sort()
                if len(temp)%2==0:
                    temp.append(0)
                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: Wrong Answer

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)

temp=[[0 for j in range(len(edge[i])-1)] for i in range(N)]
temp[0].append(0)
for i in range(1,N):
    if len(temp[i])%2==0:
        temp[i].append(0)
if len(temp[0])%2==1:
    temp[0].append(0)

def clear():
    for i in range(N):
        temp[i].sort()
        for j in range(len(temp[i])):
            temp[i][j]=0

start=0
end=N-1
while end-start>1:
    t=(end+start)//2
    clear()
    end=t

print(end)

Submission status: Wrong Answer

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)

temp=[[0 for j in range(len(edge[i])-1)] for i in range(N)]
temp[0].append(0)
for i in range(1,N):
    if len(temp[i])%2==0:
        temp[i].append(0)
if len(temp[0])%2==1:
    temp[0].append(0)

def clear():
    for i in range(N):
        for j in range(len(temp[i])):
            temp[i][j]=0

start=0
end=N-1
while end-start>1:
    t=(end+start)//2
    clear()
    end=t

print(end)

Submission status: Wrong Answer

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: Wrong Answer

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) 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: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(200000)
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: Wrong Answer

Solution code:
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[0] + 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: Wrong Answer

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つ短い長さが残る
    i = bisect_right(S,x//2)
    lower = S[:i][::-1]; upper = S[i:]
    cand = []
    rest = []
    seg = 0
    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)
    lower += cand
    L = len(lower)
    q,r = divmod(L,2)
    if r:
        return seg + len(rest) + q, lower[0]
    else:
        seg += q
        if rest:
            y = rest[-1]
            if x == y:
                return seg + len(rest), 0
            else:
                return seg + len(rest) - 1, y
        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: Time Limit Exceeded

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)

temp=[[0 for j in range(len(edge[i])-1)] for i in range(N)]
temp[0].append(0)
for i in range(1,N):
    if len(temp[i])%2==0:
        temp[i].append(0)
if len(temp[0])%2==1:
    temp[0].append(0)

def clear():
    for i in range(N):
        for j in range(len(temp[i])):
            temp[i][j]=0

def dfs(v,pv,n):
    #print(v,pv,len(edge[v]))
    if v!=0:
        if len(edge[v])==1:
            return 1
        id=0
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return -1
                temp[v][id]=r
                id+=1
        temp[v].sort()
        start=0
        end=len(temp[v])-1
        k=len(temp[v])//2
        while end-start>1:
            test=(end+start)//2
            check=True
            s=0
            t=len(temp[v])-1
            while t>s:
                if s==test:
                    s+=1
                elif t==test:
                    t-=1
                else:
                    if temp[v][s]+temp[v][t]>n:
                        check=False
                    s+=1
                    t-=1
            if check:
                end=test
            else:
                start=test
        check=True
        s=0
        t=len(temp[v])-1
        while t>s:
            if s==start:
                s+=1
            elif t==start:
                t-=1
            else:
                if temp[v][s]+temp[v][t]>n:
                    check=False
                s+=1
                t-=1
        if check:
            return temp[v][start]+1
        else:
            check=True
            s=0
            t=len(temp[v])-1
            while t>s:
                if s==end:
                    s+=1
                elif t==end:
                    t-=1
                else:
                    if temp[v][s]+temp[v][t]>n:
                        check=False
                    s+=1
                    t-=1
            if check:
                return temp[v][end]+1
            else:
                return -1
    else:
        id=0
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return False
                temp[v][id]=r
                id+=1
        temp[v].sort()
        k=len(temp[v])//2
        for i in range(k):
            test=temp[v][i]+temp[v][-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
    clear()
    if dfs(0,-1,t):
        end=t
    else:
        start=t

print(A,end)

Submission status: Time Limit Exceeded

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)
        temp.sort()
        start=0
        end=len(temp)-1
        k=len(temp)//2
        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:
            return 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:
                return temp[end]+1
            else:
                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: Time Limit Exceeded

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)
        temp.sort()
        start=0
        end=len(temp)
        k=len(temp)//2
        while end-start>1:
            test=(end+start)//2
            check=True
            ttt=temp[:test]+temp[test+1:]
            for i in range(k):
                if ttt[i]+ttt[-i-1]>n:
                    check=False
            if check:
                end=test
            else:
                start=test
        check=True
        ttt=temp[:start]+temp[start+1:]
        for i in range(k):
            if ttt[i]+ttt[-i-1]>n:
                check=False
        if check:
            return temp[start]+1
        else:
            check=True
            ttt=temp[:end]+temp[end+1:]
            for i in range(k):
                if ttt[i]+ttt[-i-1]>n:
                    check=False
            if check:
                return temp[end]+1
            else:
                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: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
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)

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(u=0, ou=-1):
        dist_leaf = 0
        for ku in to[u]:
            if ku == ou: continue
            dist_leaf += dfs(ku, u) + 1
        if dist_leaf >= 0:
            if len(to[ou]) == 2 and ou != 0:
                return dist_leaf
            else:
                dp_original[u] = dist_leaf
                return -10
        odr_dp.append(u)
        parent[u] = ou
        return -10

    def check(m):
        dp = dp_original[:]
        for u in odr_dp:
            dists = []
            for v in to[u]:
                if v == parent[u]: continue
                dists.append(dp[v] + 1)
            dists.sort()
            if dists[-1] > m:
                return False
            n_dists = len(dists)

            # 子が偶数のとき、子だけでマッチングできるか確認
            if n_dists % 2 == 0:
                for i in range(n_dists // 2):
                    if dists[i] + dists[n_dists - 1 - i] > m:
                        n_dists -= 1
                        break
                else:
                    dp[u] = 0
                    continue

            # 外す子を二分探索
            l, r = -1, n_dists
            while l + 1 < r:
                c = (l + r) // 2
                i, j = 0, n_dists - 1
                for _ in range(n_dists // 2):
                    if i == c: i += 1
                    if j == c: j -= 1
                    if dists[i] + dists[j] > m:
                        if c == n_dists - 1:
                            return False
                        l = c
                        break
                    i, j = i + 1, j - 1
                else:
                    r = c
            dp[u] = dists[r]
        #print(dp)
        if len(to[0]) % 2 == 0 and dp[0] > 0:
            return False
        else:
            return True

    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

    # DPの順番決め
    odr_dp = []
    dp_original = [inf] * n
    parent = [-1] * n
    dfs()
    #print(odr_dp)
    #print(dp_original)

    # ans_b決め
    l = 0
    r = n
    while l + 1 < r:
        m = (l + r) // 2
        if check(m):
            r = m
        else:
            l = m
    ans_b = r
    print(ans_a, ans_b)

main()