結果

問題 No.1038 TreeAddQuery
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:21:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,222 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 236,364 KB
最終ジャッジ日時 2025-03-31 17:22:17
合計ジャッジ時間 9,412 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    N, Q = int(input[idx]), int(input[idx+1])
    idx +=2
    edges = [[] for _ in range(N+1)]  # 1-based
    for _ in range(N-1):
        a, b = int(input[idx]), int(input[idx+1])
        edges[a].append(b)
        edges[b].append(a)
        idx +=2
    queries = []
    for _ in range(Q):
        X = int(input[idx])
        Y = int(input[idx+1])
        Z = int(input[idx+2])
        queries.append((X,Y,Z))
        idx +=3
    
    value = [0]*(N+1)  # initial values are 0
    
    for X_i, Y_i, Z_i in queries:
        # Output current value of X_i
        print(value[X_i])
        
        # Add Z_i to all nodes within Y_i distance of X_i
        visited = [False]*(N+1)
        q = deque()
        q.append((X_i, 0))
        visited[X_i] = True
        while q:
            node, d = q.popleft()
            value[node] += Z_i
            if d == Y_i:
                continue
            for neighbor in edges[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    q.append((neighbor, d+1))
                    
if __name__ == "__main__":
    main()
0