Problem p03949 (python)

Fixed submission:
import sys
import heapq
o=lambda:map(int,raw_input().split())
n=int(raw_input())
e=[[] for _ in range(n+1)]
for _ in range(n-1):a,b=o();e[a]+=[(b,1)];e[b]+=[(a,1)]
k=int(raw_input())
for _ in range(k):v,p=o();e[v]+=[(0,p)];e[0]+=[(v,p)]
vis=[False]*(n+1)
cost=[10**9]*(n+1)
q=[(0,0)]
heapq.heapify(q)
while len(q):
    c,v=heapq.heappop(q)
    vis[v]=True
    cost[v]=c
    for (w,d) in e[v]:
        if not vis[w] and c+d<cost[w]:
            heapq.heappush(q,(c+d,w))
            cost[w]=c+d
for i in range(1,n+1):
    for w,d in e[i]:
        if w!=0 and abs(cost[i]-cost[w])!=1:print 'No';sys.exit()
print 'Yes'
for i in range(n):print cost[i+1]

Buggy submission (verdict: Runtime Error):
import sys
import heapq
o=lambda:map(int,raw_input().split())
n=int(raw_input())
e=[[] for _ in range(n+1)]
for _ in range(n-1):a,b=o();e[a]+=[(b,1)];e[b]+=[(a,1)]
k=int(raw_input())
for _ in range(k):v,p=o();e[v]+=[(0,p)];e[0]+=[(v,p)]
vis=[False]*n
q=[(0,0)]
heapq.heapify(q)
while len(q):
    c,v=heapq.heappop(q)
    vis[v]=True
    cost[v]=c
    for (w,d) in e[v]:
        if not vis[w]:q+=[(c+d,w)]
for i in range(n):
    for w,d in e[i]:
        if abs(cost[i]-cost[w])!=1:print 'No';sys.exit()
print 'Yes'
for i in range(n):print cost[i]

Buggy submission (verdict: Runtime Error):
import sys
import heapq
sys.setrecursionlimit(200000)
o=lambda:map(int,raw_input().split())
n=int(raw_input())
e=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=o()
    e[a]+=[(b,1)];e[b]+=[(a,1)]
k=int(raw_input())
for _ in range(k):
    v,p=o()
    e[v]+=[(0,p)];e[0]+=[(v,p)]
vis=[False]*n
q=[(0,0)]
heapq.heapify(q)
while len(q):
    c,v=heapq.heappop(q)
    vis[v]=True
    cost[v]=c
    for (w,d) in e[v]:
        if not vis[w]:q+=[(c+d,w)]
for i in range(n):
    for w,d in e[i]:
        if abs(cost[i]-cost[w])!=1:print 'No';sys.exit()
print 'Yes'
for i in range(n):print cost[i]

Buggy submission (verdict: Runtime Error):
import sys
import heapq
sys.setrecursionlimit(200000)
o=lambda:map(int,raw_input().split())
n=int(raw_input())
e=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=o()
    e[a]+=[(b,1)];e[b]+=[(a,1)]
k=int(raw_input())
for _ in range(k):
    v,p=o()
    e[v]+=[(0,p)];e[0]+=[(v,p)]
vis=[False]*n
q=[(0,0)]
heapq.heapify(q)
while len(q):
    c,v=heapq.heappop(q)
    vis[v]=True
    cost[v]=c
    for (w,d) in e[v]:
        if not vis[w]:q+=[(c+d,w)]
for i in range(n):
    for w,d in e[i]:
        if abs(cost[i]-cost[w])!=1:print 'No';sys.exit()
print 'Yes'
for i in range(n):print cost[i]

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(200000)
o=lambda:map(int,raw_input().split())
n=int(raw_input())
e=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=o()
    e[a-1]+=[b-1];e[b-1]+=[a-1]
k=int(raw_input())
INF=float('inf')
r=[(-INF,INF)for _ in range(n)]
for _ in range(k):
    v,p=o()
    r[v-1]=(p,p)
vis=[False]*n
def dfs(x):
    vis[x]=True
    r1,r2=r[x]
    for w in e[x]:
        if not vis[w]:
            dfs(w)
            w1,w2=r[w]
            if w1==-INF or r1==-INF or (w1-r1)%2:r1=max(r1,w1-1);r2=min(r2,w2+1)
            else: r1,r2=1,-1
    if r1>r2:r1,r2=1,-1
    return=(r1,r2)
dfs(0)
if r[0]==(1,-1):print 'No';sys.exit()
print 'Yes'
vis=[False]*n
q=[(0,r[0][0])]
ans=[0]*n
while len(q):
    v,c=q.pop(0)
    vis[v]=True
    ans[v]=c
    for w in e[v]:
        if not vis[w]:
            for x in (c+1,c-1):
                if r[w][0]<=x<=r[w][1]:q+=[(w,x)];break
for i in range(n):print int(ans[i])

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(200000)
o=lambda:map(int,raw_input().split())
n=int(raw_input())
e=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=o()
    e[a-1]+=[b-1];e[b-1]+=[a-1]
k=int(raw_input())
INF=float('inf')
r=[(-INF,INF)for _ in range(n)]
for _ in range(k):
    v,p=o()
    r[v-1]=(p,p)
vis=[False]*n
def dfs(x):
    vis[x]=True
    r1,r2=r[x]
    for w in e[x]:
        if not vis[w]:
            dfs(w)
            w1,w2=r[w]
            if w1==-INF or r1==-INF or (w1-r1)%2:r1=max(r1,w1-1);r2=min(r2,w2+1)
            else: r1,r2=1,-1
    return=(r1,r2)
dfs(0)
if r[0]==(1,-1):print 'No';sys.exit()
print 'Yes'
vis=[False]*n
q=[(0,r[0][0])]
ans=[0]*n
while len(q):
    v,c=q.pop(0)
    vis[v]=True
    ans[v]=c
    for w in e[v]:
        if not vis[w]:
            for x in (c+1,c-1):
                if r[w][0]<=x<=r[w][1]:q+=[(w,x)];break
for i in range(n):print int(ans[i])