ABC138D 根付き木の累積和の問題

Question

https://atcoder.jp/contests/abc138/tasks/abc138_d
についての質問です

問題文
1 から N までの番号がついた N 個の頂点を持つ根付き木が与えられます。 この木の根は頂点 1 で、 番目の辺 (1≤≤N−1) は頂点 aと頂点 b
を結びます。
各頂点にはカウンターが設置されており、はじめすべての頂点のカウンターの値は 0 です。
これから、以下のような Q 回の操作が行われます。
操作 (1≤≤Q): 頂点 p を根とする部分木に含まれるすべての頂点のカウンターの値に x を足す。
すべての操作のあとの各頂点のカウンターの値を求めてください。

ACしないコード

n, q = map(int, input().split())

arr = [[] for i in range(n)]
for _ in range(n-1):
  a, b = map(int,input().split())
  arr[a-1].append(b-1)
  
ans = [0 for i in range(n)]
for _ in range(q):
  p, v = map(int,input().split())
  ans[p-1] += v

q = [0]
while q:
  t = q.pop(-1)
  for j in arr[t]:
    ans[j] += ans[t]
    q.append(j)

print(*ans)

ACする変更後のコード

import sys
sys.setrecursionlimit(10**9)
n, q = map(int, input().split())

arr = [[] for i in range(n)]
for _ in range(n-1):
  a, b = map(int,input().split())
  a -= 1
  b -= 1
  # 双方向に変更
  arr[a].append(b)
  arr[b].append(a)

ans = [0 for i in range(n)]
for _ in range(q):
  p, v = map(int,input().split())
  p -= 1
  ans[p] += v
# dfsで算出
def dfs(v,p):
  for i in arr[v]:
    if i == p:
      continue
    ans[i] += ans[v]
    dfs(i,v)
              
dfs(0,-1)
print(*ans)

なぜACにならないのかわかりません。

木構造を双方向にする点とdfsでなければ求められない理由を教えていただけないでしょうか

Answer 1

AtCoder ABC138D [Python3] どこが間違っているのかご教授ください
https://teratail.com/questions/223681

以前にも同じような質問がありましたが、おそらく同じ勘違いをしています。根が決まっている以外はでたらめな順番・向きで辺が与えられると気づけば最初のコードではだめだとわかると思います。

after_contestと名前の付いたテストケース以外は決まった向きで辺が与えられるので、それがACであれば勘違い以外に問題はないと考えていいと思います。

Comments

[afushi]

ありがとうございます。以前にも同じ質問した方がいらっしゃったのですね。

勉強になりました。

Answer 2

例えばｍ、入力データを以下で実行してみます。

4 3
2 1
3 2
4 1
2 10
3 100
4 1000

ACしないコード

>>> n, q = map(int, input().split())
>>>
>>> arr = [[] for i in range(n)]
>>> for _ in range(n-1):
...   a, b = map(int,input().split())
...   arr[a-1].append(b-1)
...
>>> ans = [0 for i in range(n)]
>>> for _ in range(q):
...   p, v = map(int,input().split())
...   ans[p-1] += v
...
>>> for i,A in enumerate(arr):
...   for j in A:
...     ans[j] += ans[i]
...
>>> print(*ans)
1010 110 100 1000

ACする変更後のコード

>>> import sys
>>> sys.setrecursionlimit(10**9)
>>> n, q = map(int, input().split())
>>>
>>> arr = [[] for i in range(n)]
>>> for _ in range(n-1):
...   a, b = map(int,input().split())
...   a -= 1
...   b -= 1
...   # 双方向に変更
...   arr[a].append(b)
...   arr[b].append(a)
...
>>> ans = [0 for i in range(n)]
>>> for _ in range(q):
...   p, v = map(int,input().split())
...   p -= 1
...   ans[p] += v
...
>>> # dfsで算出
>>> def dfs(v,p):
...   for i in arr[v]:
...     if i == p:
...       continue
...     ans[i] += ans[v]
...     dfs(i,v)
...
>>> dfs(0,-1)
>>> print(*ans)
0 10 110 1000

実行結果が違うのですから「自分はどちらも結果は変わらないように思う」というのが間違いです。
理由はまず自分で考えてみたほうが良いでしょう。

Comments

[afushi]

この木の根は頂点 1 で、
という前提と
4 3
2 1
3 2
4 1
2 10
3 100
4 1000
というinputは成り立つのでしょうか、
2 1だと根が１なのに親がいる状態になると思うんですが、、

[afushi]

木が順番に根にくっついているわけではないことに気づき、
答えを算出する部分を
q = [0]
while q:
t = q.pop(-1)
for j in arr[t]:
ans[j] += ans[t]
q.append(j)

に変更しましたがまだACになりません。
何を見落としているのでしょうか

[ppaul]

同じ入力データで実行すると、
>>> print(*ans)
0 10 100 1000
ですね。
この数字を見て考えてください。