Problem p02936 (python)

Fixed submission:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

if 'LOCAL' in os.environ:
    N = 2* 10** 5
    Q = 2 * 10 ** 5
    AB = [[i, i + 1] for i in range(1, N)]
    PX = [[i, 10] for i in range(Q)]
else:
    N, Q = LI()
    AB = []
    PX = []
    for i in range(N-1):
        AB.append(LI())

    for i in range(Q):
        PX.append(LI())


"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？

カウントを若い順にやっていく
"""
AB = sorted(AB, key=lambda x: x[0])
perr('AB')
perr(AB)
d = {}
for p, x in PX:
    if p not in d.keys():
        d[p] = 0
    d[p] += x
for a, b in AB:
    if b not in d.keys():
        d[b] = 0
    if a not in d.keys():
        d[a] = 0
    d[b] += d[a]
for i in range(1, N+1):
    print(d[i], end=' ')

Buggy submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

ans = []
lines_dict =None
d=None
def main():
    global AB, PX
    if 'LOCAL' in os.environ:
        N = 2* 10** 5
        Q = 2 * 10 ** 5
        AB = [[i, i + 1] for i in range(1, N)]
        PX = [[i, 10] for i in range(Q)]
    else:
        N, Q = LI()
        AB = {}
        PX = {}
        for i in range(N-1):
            #  AB.append(LI())
            a, b = LI()
            if a not in AB.keys():
                AB[a] = set()
            if b not in AB.keys():
                AB[b] = set()
            AB[a].add(b)
            AB[b].add(a)

        for i in range(Q):
            p, x = LI()
            if p not in PX.keys():
                PX[p] = 0
            PX[p] += x
        perr(AB)
        perr(PX)
        dfs(1, -1)
        for i in sorted(PX.keys()):
            print(PX[i], end=' ')
        #  ans = [0 for _ in range(N)]

def dfs(parent, parent_parent):
    perr(PX)
    for node in AB[parent]:
        if node != parent_parent:
            perr(node)
            if node not in PX.keys():
                PX[node] = 0
            PX[node] += PX[parent]
            dfs(node, parent)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

ans = []
lines_dict =None
d=None
def main():
    global AB, PX
    if 'LOCAL' in os.environ:
        N = 2* 10** 5
        Q = 2 * 10 ** 5
        AB = [[i, i + 1] for i in range(1, N)]
        PX = [[i, 10] for i in range(Q)]
    else:
        N, Q = LI()
        AB = {}
        PX = {}
        for i in range(N-1):
            #  AB.append(LI())
            a, b = LI()
            if a not in AB.keys():
                AB[a] = set()
            if b not in AB.keys():
                AB[b] = set()
            AB[a].add(b)
            AB[b].add(a)

        for i in range(Q):
            p, x = LI()
            if p not in PX.keys():
                PX[p] = 0
            PX[p] += x
        perr(AB)
        perr(PX)
        dfs(1, -1)
        for i in sorted(PX.keys()):
            print(PX[i], end=' ')
        #  ans = [0 for _ in range(N)]

def dfs(parent, parent_parent):
    perr(PX)
    for node in AB[parent]:
        if node != parent_parent:
            perr(node)
            if node not in PX.keys():
                PX[node] = 0
            PX[node] += PX[parent]
            dfs(node, parent)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

if 'LOCAL' in os.environ:
    N = 2* 10** 5
    Q = 2 * 10 ** 5
    AB = [[i, i + 1] for i in range(1, N)]
    PX = [[i, 10] for i in range(Q)]
else:
    N, Q = LI()
    AB = []
    PX = []
    for i in range(N-1):
        #  AB.append(LI())
        AB.append(LI())

    for i in range(Q):
        PX.append(LI())


"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？

カウントを若い順にやっていく
"""
#  AB = sorted(AB, key=lambda x: x[0])
#  perr('AB')
#  perr(AB)
d = {}
for i in range(N+1):
    d[i] = 0
for p, x in PX:
    if p not in d.keys():
        d[p] = 0
    d[p] += x
perr(d)
"""
根からスタートするとは？
1-5-3とかっていう組み合わせがあるため、dfsで根から辿っていく必要がある

"""
ans = [0 for _ in range(N)]
ans[0] = d[1]

lines_dict = {}
for ab in AB:
    if ab[0] not in lines_dict.keys():
        lines_dict[ab[0]] = [ab[1]]
    else:
        lines_dict[ab[0]].append(ab[1])

    if ab[1] not in lines_dict.keys():
        lines_dict[ab[1]] = [ab[0]]
    else:
        lines_dict[ab[1]].append(ab[0])

pdb.set_trace()
perr(lines_dict)
#  exit()


def dfs(current_node, val, parent_node):
    for other_node in lines_dict[current_node]:
        if other_node == parent_node:
            continue
        # まだ訪れていないので訪問
        new_val = val + d[other_node]
        ans[other_node-1] = new_val
        dfs(other_node, new_val, current_node)


    #  new_AB = []
    #  target_lines = []
    #  for ab in AB:
    #      if current_node in ab and ab[0] not in done_list and ab[1] not in done_list:
    #          target_lines.append(ab)
    #      else:
    #          new_AB.append(ab)
    #  target_lines = [ab for ab in AB if current_node in ab and ab[0] not in done_list and ab[1] not in done_list]
    #  if current_node not in lines_dict.keys():
    #      return
    #  target_lines = [num for num in lines_dict[current_node] if num not in done_list]
    #  done_list.append(current_node)
    #  for to_node in target_lines:
    #      perr(to_node)
    #      ans[to_node-1] = val + d[to_node]
    #      dfs(to_node, ans[to_node-1], done_list)


dfs(1, d[1], None)
perr(ans)
print(' '.join(map(lambda x: str(x), ans)))

Buggy submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

if 'LOCAL' in os.environ:
    N = 2* 10** 5
    Q = 2 * 10 ** 5
    AB = [[i, i + 1] for i in range(1, N)]
    PX = [[i, 10] for i in range(Q)]
else:
    N, Q = LI()
    AB = []
    PX = []
    for i in range(N-1):
        #  AB.append(LI())
        AB.append(LI())

    for i in range(Q):
        PX.append(LI())


"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？

カウントを若い順にやっていく
"""
#  AB = sorted(AB, key=lambda x: x[0])
#  perr('AB')
#  perr(AB)
d = {}
for i in range(N+1):
    d[i] = 0
for p, x in PX:
    if p not in d.keys():
        d[p] = 0
    d[p] += x
perr(d)
"""
根からスタートするとは？
1-5-3とかっていう組み合わせがあるため、dfsで根から辿っていく必要がある

"""
ans = [0 for _ in range(N)]
ans[0] = d[1]

lines_dict = {}
for ab in AB:
    if ab[0] not in lines_dict.keys():
        lines_dict[ab[0]] = [ab[1]]
    else:
        lines_dict[ab[0]].append(ab[1])

    if ab[1] not in lines_dict.keys():
        lines_dict[ab[1]] = [ab[0]]
    else:
        lines_dict[ab[1]].append(ab[0])

pdb.set_trace()
perr(lines_dict)
#  exit()


def dfs(current_node, val, parent_node):
    for other_node in lines_dict[current_node]:
        if other_node == parent_node:
            continue
        # まだ訪れていないので訪問
        new_val = val + d[other_node]
        ans[other_node-1] = new_val
        dfs(other_node, new_val, current_node)


    #  new_AB = []
    #  target_lines = []
    #  for ab in AB:
    #      if current_node in ab and ab[0] not in done_list and ab[1] not in done_list:
    #          target_lines.append(ab)
    #      else:
    #          new_AB.append(ab)
    #  target_lines = [ab for ab in AB if current_node in ab and ab[0] not in done_list and ab[1] not in done_list]
    #  if current_node not in lines_dict.keys():
    #      return
    #  target_lines = [num for num in lines_dict[current_node] if num not in done_list]
    #  done_list.append(current_node)
    #  for to_node in target_lines:
    #      perr(to_node)
    #      ans[to_node-1] = val + d[to_node]
    #      dfs(to_node, ans[to_node-1], done_list)


dfs(1, d[1], None)
perr(ans)
print(' '.join(map(lambda x: str(x), ans)))

Buggy submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

if 'LOCAL' in os.environ:
    N = 2* 10** 5
    Q = 2 * 10 ** 5
    AB = [[i, i + 1] for i in range(1, N)]
    PX = [[i, 10] for i in range(Q)]
else:
    N, Q = LI()
    AB = []
    PX = []
    for i in range(N-1):
        #  AB.append(LI())
        AB.append(sorted(LI()))

    for i in range(Q):
        PX.append(LI())


"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？

カウントを若い順にやっていく
"""
AB = sorted(AB, key=lambda x: x[0])
perr('AB')
perr(AB)
d = {}
for i in range(N+1):
    d[i] = 0
for p, x in PX:
    if p not in d.keys():
        d[p] = 0
    d[p] += x

"""
根からスタートするとは？
1-5-3とかっていう組み合わせがあるため、dfsで根から辿っていく必要がある

"""
ans = [0 for _ in range(N)]
ans[0] = d[1]
def dfs(current_node, val, done_list):
    target_lines = [_ for _ in AB if current_node in _ and not any(n in done_list for n in _)]
    done_list.append(current_node)
    for line in target_lines:
        perr(line)
        if line[0] == current_node:
            new_node = line[1]
        else:
            new_node = line[0]
        ans[new_node-1] = val + d[new_node]
        dfs(new_node, ans[new_node-1], done_list)

dfs(1, d[1], [])
perr(ans)
for a in ans:
    print(a, end=' ')