abc138 D問題がめちゃくちゃ勉強になった話(python用)

abc138のD問題KIがよかったよって話

自分用：dfs、再帰、入力でreもしくはTLE吐いたらここに来るのです

とりあえずソースコード

ki.py

import sys
sys.setrecursionlimit(10 ** 6)
import sys
def input():
    return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
#print(graph)
for _ in range(Q):
    a , b = map(int,input().split())
    a = a - 1
    point[a] += b
# dfsを用いて累積和を計算する
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:
        # 次のノードが前に参照した値の時はcontinue
        if next == prev:
            continue
        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]
        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)

dfs(0)
print(*point)

何がよかったか

1. dfsの書き方を勉強できたこと
   2. デフォルト引数実際に使ったお
2. 配列の参照以外でreの原因探しができたこと
3. 入力の速度意外と大事だねってこと

やったこと

1.dfsの書き方を勉強できたこと

使ってる人は分かっていると思うが累積和とdfsの複合問題を扱えたこと。
慣れてないうちはforと再帰のループの区別が大変そう

# dfsを用いて累積和を計算する
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:
        # 次のノードが前に参照した値の時はcontinue
        if next == prev:
            continue
        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]
        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)

dfs(0)

2.配列の参照以外でreの原因探しができたこと

噂に聞いていたpythonにおける再帰限界の問題を完全に忘れていた。
実際のコンテストでこれ描き忘れてたら泣きそう

import sys
sys.setrecursionlimit(10 ** 6)

3.入力の速度意外と大事だねってこと

今回は入力が2 * 10 ** 5だったので入力自体でなかなか時間がかかってTLE吐いていた。
普段気にしてなかったけど10 ** 5くらいになったら意識的にimport sysしないとダメだね

import sys
def input():
    return sys.stdin.readline()[:-1]

まとめ

dfsやれ
再帰上限考えろ
入力の速度をバカにできんよ
（困ったらここコピペしてえ）

PS:こうやったらもっと早くなるよってことあったら教えてください（速さこそ正義）