質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

2回答

611閲覧

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

afushi

総合スコア2

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2021/09/09 05:56

編集2021/09/09 07:47

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

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

ACしないコード

python

1n, q = map(int, input().split()) 2 3arr = [[] for i in range(n)] 4for _ in range(n-1): 5 a, b = map(int,input().split()) 6 arr[a-1].append(b-1) 7 8ans = [0 for i in range(n)] 9for _ in range(q): 10 p, v = map(int,input().split()) 11 ans[p-1] += v 12 13q = [0] 14while q: 15 t = q.pop(-1) 16 for j in arr[t]: 17 ans[j] += ans[t] 18 q.append(j) 19 20print(*ans)

ACする変更後のコード

python

1import sys 2sys.setrecursionlimit(10**9) 3n, q = map(int, input().split()) 4 5arr = [[] for i in range(n)] 6for _ in range(n-1): 7 a, b = map(int,input().split()) 8 a -= 1 9 b -= 1 10 # 双方向に変更 11 arr[a].append(b) 12 arr[b].append(a) 13 14ans = [0 for i in range(n)] 15for _ in range(q): 16 p, v = map(int,input().split()) 17 p -= 1 18 ans[p] += v 19# dfsで算出 20def dfs(v,p): 21 for i in arr[v]: 22 if i == p: 23 continue 24 ans[i] += ans[v] 25 dfs(i,v) 26 27dfs(0,-1) 28print(*ans)

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

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

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

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

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

投稿2021/09/09 14:38

yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

afushi

2021/09/09 16:13

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

0

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

plain

14 3 22 1 33 2 44 1 52 10 63 100 74 1000

ACしないコード

python

1>>> n, q = map(int, input().split()) 2>>> 3>>> arr = [[] for i in range(n)] 4>>> for _ in range(n-1): 5... a, b = map(int,input().split()) 6... arr[a-1].append(b-1) 7... 8>>> ans = [0 for i in range(n)] 9>>> for _ in range(q): 10... p, v = map(int,input().split()) 11... ans[p-1] += v 12... 13>>> for i,A in enumerate(arr): 14... for j in A: 15... ans[j] += ans[i] 16... 17>>> print(*ans) 181010 110 100 1000

ACする変更後のコード

python

1>>> import sys 2>>> sys.setrecursionlimit(10**9) 3>>> n, q = map(int, input().split()) 4>>> 5>>> arr = [[] for i in range(n)] 6>>> for _ in range(n-1): 7... a, b = map(int,input().split()) 8... a -= 1 9... b -= 1 10... # 双方向に変更 11... arr[a].append(b) 12... arr[b].append(a) 13... 14>>> ans = [0 for i in range(n)] 15>>> for _ in range(q): 16... p, v = map(int,input().split()) 17... p -= 1 18... ans[p] += v 19... 20>>> # dfsで算出 21>>> def dfs(v,p): 22... for i in arr[v]: 23... if i == p: 24... continue 25... ans[i] += ans[v] 26... dfs(i,v) 27... 28>>> dfs(0,-1) 29>>> print(*ans) 300 10 110 1000

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

投稿2021/09/09 06:34

ppaul

総合スコア24666

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

afushi

2021/09/09 07:14

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

2021/09/09 07:46

木が順番に根にくっついているわけではないことに気づき、 答えを算出する部分を q = [0] while q: t = q.pop(-1) for j in arr[t]: ans[j] += ans[t] q.append(j) に変更しましたがまだACになりません。 何を見落としているのでしょうか
ppaul

2021/09/09 12:47

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問