ABC138 D-Ki 復習

そうか、毎回木をたどってたからTLEになったのか
全部読んでからまとめて木をたどればいいんだな

書き直してみた
解説とテストに修正が入ってて、無向グラフとして扱わないとWAになってしまうので
その対応も入れて

あと、
input()だとTLEになるのでstdin.readline()に変更したらかなり速くなってAC
forで回してcntを出力してたのをprint(*cnt[1:])にかえたのも少し速くなった
引数が何万個にもなるわけなので気が引けてたけど大丈夫みたい

from sys import stdin, setrecursionlimit

def main():

    def walk(p, c):
        if visited[p]:
            return
        visited[p] = True
        cnt[p] += c
        for n in tree[p]:
            walk(n, cnt[p])

    setrecursionlimit(2000001)

    n, q = [int(x) for x in stdin.readline().split()]

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

    cnt = [0] * (n + 1)
    for _ in range(q):
        p, x = [int(x) for x in stdin.readline().split()]
        cnt[p] += x

    visited = [False] * (n + 1)
    walk(1, 0)

    print(*cnt[1:])

main()

あと試してみたこと

setrecursionlimitを1000000から200001に減らす
変わらない
メモリ使用量も変わらない

from sys import stdin/stdin.readline()を
import sys/sys.stdin.readline()に変更
変わらない

sys.stdin.readline()を
rl = sys.stdin.readline/rl()に変更
ほんの少し速くなったかもしれない？
でも気のせいかもしれない