結果
問題 |
No.1038 TreeAddQuery
|
ユーザー |
![]() |
提出日時 | 2025-06-12 18:06:03 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,328 bytes |
コンパイル時間 | 243 ms |
コンパイル使用メモリ | 81,936 KB |
実行使用メモリ | 80,596 KB |
最終ジャッジ日時 | 2025-06-12 18:07:42 |
合計ジャッジ時間 | 8,650 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 TLE * 1 -- * 18 |
ソースコード
import sys from collections import deque def main(): input = sys.stdin.read().split() ptr = 0 N, Q = int(input[ptr]), int(input[ptr+1]) ptr += 2 # Build adjacency list adj = [[] for _ in range(N+1)] # 1-based for _ in range(N-1): a = int(input[ptr]) b = int(input[ptr+1]) adj[a].append(b) adj[b].append(a) ptr += 2 # Precompute answers for each query ans = [] # To track the current value of each node values = [0] * (N + 1) for _ in range(Q): X = int(input[ptr]) Y = int(input[ptr+1]) Z = int(input[ptr+2]) ptr += 3 # Output current value of X ans.append(str(values[X])) # BFS to find all nodes within Y distance from X visited = [False] * (N + 1) q = deque() q.append((X, 0)) visited[X] = True nodes_to_update = [] while q: u, d = q.popleft() nodes_to_update.append(u) if d < Y: for v in adj[u]: if not visited[v]: visited[v] = True q.append((v, d+1)) # Update the values for u in nodes_to_update: values[u] += Z print('\n'.join(ans)) if __name__ == '__main__': main()