結果

問題 No.1038 TreeAddQuery
ユーザー gew1fw
提出日時 2025-06-12 20:25:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,252 bytes
コンパイル時間 235 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 82,260 KB
最終ジャッジ日時 2025-06-12 20:25:52
合計ジャッジ時間 8,505 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read
    data = input().split()
    idx = 0

    N = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1

    # Build adjacency list
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u = int(data[idx])
        idx += 1
        v = int(data[idx])
        idx += 1
        adj[u].append(v)
        adj[v].append(u)
    
    # Weights initialized to 0
    weights = [0] * (N + 1)
    
    for _ in range(Q):
        X = int(data[idx])
        idx += 1
        Y = int(data[idx])
        idx += 1
        Z = int(data[idx])
        idx += 1
        
        # Step 1: Output current weight of X
        print(weights[X])
        
        # Step 2: Add Z to all nodes within Y distance from X
        visited = set()
        q = deque()
        q.append( (X, 0) )
        visited.add(X)
        
        while q:
            u, d = q.popleft()
            if d > Y:
                continue
            weights[u] += Z
            for v in adj[u]:
                if v not in visited and d + 1 <= Y:
                    visited.add(v)
                    q.append( (v, d + 1) )

if __name__ == "__main__":
    main()
0