Problem p03484 (python)

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

Buggy submission (verdict: Runtime Error):
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")

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)