Problem p03949 (python)

Fixed submission:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc063/tasks/arc063_c

数字が置かれている頂点は範囲指定の制約になる
→制約をすべての点に伝播させれば、後はその範囲内から適当に選んで実装すればよい

一度根方向に制約を集め、それを全方位に伝播させればよい？
→それっぽさそう

偶奇に関してはちゃんと考えてね
→条件の両端の偶奇で判断可能
"""

import sys
sys.setrecursionlimit(5*10**5)

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)


l = [float("-inf")] * N
r = [float("inf")]  * N

K = int(input())

for i in range(K):

    V,P = map(int,input().split())
    V -= 1
    l[V] = P
    r[V] = P

#dfsで条件を根方向に集める
def dfs(v,p):

    for nex in lis[v]:

        if nex != p:
            nl,nr = dfs(nex,v)

            if l[v] != float("-inf") and nl != float("-inf") and l[v] % 2 != nl % 2:
                print ("No")
                sys.exit()

            l[v] = max(l[v] , nl)
            r[v] = min(r[v] , nr)

            if l[v] > r[v]:
                print ("No")
                sys.exit()

    return l[v] - 1 , r[v] + 1

dfs(0,0)

#bfsで条件を配る
from collections import deque
q = deque([0])
unvisit = [True] * N
ans = [None] * N
ans[0] = l[0]

while len(q) > 0:
    
    v = q.popleft()
    unvisit[v] = False

    if l[v] > r[v]:
        print ("No")
        sys.exit()
    
    for nex in lis[v]:

        if unvisit[nex]:

            if l[nex] != float("-inf") and l[v] != float("-inf") and l[v] % 2 == l[nex] % 2:
                print ("No")
                sys.exit()

            l[nex] = max(l[nex] , l[v]-1)
            r[nex] = min(r[nex] , r[v]+1)
            ans[nex] = l[nex]

            q.append(nex)

print ("Yes")
for i in ans:
    print (i)

Buggy submission (verdict: Runtime Error):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc063/tasks/arc063_c

数字が置かれている頂点は範囲指定の制約になる
→制約をすべての点に伝播させれば、後はその範囲内から適当に選んで実装すればよい

一度根方向に制約を集め、それを全方位に伝播させればよい？
→それっぽさそう

偶奇に関してはちゃんと考えてね
→条件の両端の偶奇で判断可能
"""

import sys

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)


l = [float("-inf")] * N
r = [float("inf")]  * N

K = int(input())

for i in range(K):

    V,P = map(int,input().split())
    V -= 1
    l[V] = P
    r[V] = P

#dfsで条件を根方向に集める
def dfs(v,p):

    for nex in lis[v]:

        if nex != p:
            nl,nr = dfs(nex,v)

            if l[v] != float("-inf") and nl != float("-inf") and l[v] % 2 != nl % 2:
                print ("No")
                sys.exit()

            l[v] = max(l[v] , nl)
            r[v] = min(r[v] , nr)

            if l[v] > r[v]:
                print ("No")
                sys.exit()

    return l[v] - 1 , r[v] + 1

dfs(0,0)

#bfsで条件を配る
from collections import deque
q = deque([0])
unvisit = [True] * N
ans = [None] * N
ans[0] = l[0]

while len(q) > 0:
    
    v = q.popleft()
    unvisit[v] = False

    if l[v] > r[v]:
        print ("No")
        sys.exit()
    
    for nex in lis[v]:

        if unvisit[nex]:

            if l[nex] != float("-inf") and l[v] != float("-inf") and l[v] % 2 == l[nex] % 2:
                print ("No")
                sys.exit()

            l[nex] = max(l[nex] , l[v]-1)
            r[nex] = min(r[nex] , r[v]+1)
            ans[nex] = l[nex]

            q.append(nex)

print ("Yes")
for i in ans:
    print (i)