結果
問題 |
No.1038 TreeAddQuery
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()