結果
問題 |
No.1038 TreeAddQuery
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:27:37 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,241 bytes |
コンパイル時間 | 183 ms |
コンパイル使用メモリ | 82,384 KB |
実行使用メモリ | 259,232 KB |
最終ジャッジ日時 | 2025-06-12 20:27:56 |
合計ジャッジ時間 | 8,181 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 = int(input[ptr]) ptr += 1 Q = int(input[ptr]) ptr += 1 # Build the tree tree = [[] for _ in range(N+1)] for _ in range(N-1): a = int(input[ptr]) ptr +=1 b = int(input[ptr]) ptr +=1 tree[a].append(b) tree[b].append(a) # Read queries queries = [] for _ in range(Q): x = int(input[ptr]) ptr +=1 y = int(input[ptr]) ptr +=1 z = int(input[ptr]) ptr +=1 queries.append( (x, y, z) ) # Weights array weights = [0]*(N+1) for x, y, z in queries: # Output current weight of x print(weights[x]) # BFS to find all nodes within y distance visited = [False]*(N+1) q = deque() q.append( (x, 0) ) visited[x] = True while q: u, d = q.popleft() if d > y: continue weights[u] += z for v in tree[u]: if not visited[v]: visited[v] = True q.append( (v, d+1) ) if __name__ == '__main__': main()