AtCoder ABC138D [Python3] どこが間違っているのかご教授ください

Question

問題はこれです
https://atcoder.jp/contests/abc138/tasks/abc138_d

解答１ (WA)

import sys

def main():
    n, q = [int(x) for x in sys.stdin.readline().split()]
    AB = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        AB[a].append(b)

    ans = [0 for _ in range(n+1)]
    for _ in range(q):
        p, x = [int(x) for x in sys.stdin.readline().split()]
        ans[p] += x
    
    for a in range(1, n):
        for b in AB[a]:
            ans[b] += ans[a]
    
    print(' '.join(map(str, ans[1:])))

if __name__ == "__main__":
    main()

解答２ (AC)

import sys

def main():
    n, q = [int(x) for x in sys.stdin.readline().split()]
    AB = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        AB[a].append(b)
        AB[b].append(a)
    # 無向グラフとして考える

    ans = [0 for _ in range(n+1)]
    for _ in range(q):
        p, x = [int(x) for x in sys.stdin.readline().split()]
        ans[p] += x
    
    stack = [1]
    parent = [0 for _ in range(n+1)]
    while stack:
        x = stack.pop()
        for y in AB[x]:
            if y != parent[x]: # yがxの親でなければ
                parent[y] = x # xがyの親
                stack.append(y)
                ans[y] += ans[x]
 
    
    print(' '.join(map(str, ans[1:])))

if __name__ == "__main__":
    main()

一応解答２でACはしたのですが最初解答１でWAだったのが府に落ちず、考えても何がいけないのかよくわかりませんでした

Answer 1

一つ目の解法はグラフが a -> b の有向辺を持つ木だった場合
二つ目の解法はグラフが a <-> b の無向辺を持つ木だった場合というのは、コメントを読む限り理解されてるものだと思います。
勘違いしやすいですがこの問題も有向辺だとは一言も言ってないので、無向辺として解く必要があります。

実はこの問題、解説PDFでも当初有向グラフとして解説されていたのが修正されていたり、本番のテストケースだと一つ目の解法のようにa -> bと考えても通るようになっていました。
ただ問題文だけでは有向グラフだと決めつけることができないので、本番後にafter_contestというテストケースが追加され、今では一つ目のような解法がはじかれるようになっています。

Comments

[退会済みユーザー]

もう一度グラフを描いてみたら理解できました
a < b が満たされていたとしても
aが必ずしも親になるわけではないということですね
たとえば入力の一部に
4 6
5 6
のような箇所があったとして、
仮に4が６の親なら６は5の親になる
みたいなのがイメージできたので
解決しました