結果
問題 |
No.899 γatheree
|
ユーザー |
![]() |
提出日時 | 2025-05-14 12:47:22 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,045 bytes |
コンパイル時間 | 313 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 847,368 KB |
最終ジャッジ日時 | 2025-05-14 12:47:52 |
合計ジャッジ時間 | 11,444 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 MLE * 1 -- * 2 |
ソースコード
import sys from collections import deque def main(): sys.setrecursionlimit(1 << 25) input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 edges = [[] for _ in range(N)] for _ in range(N-1): u = int(input[ptr]) v = int(input[ptr+1]) ptr +=2 edges[u].append(v) edges[v].append(u) root = 0 parent = [-1] * N children = [[] for _ in range(N)] visited = [False] * N q = deque([root]) visited[root] = True while q: u = q.popleft() for v in edges[u]: if not visited[v] and v != parent[u]: parent[v] = u children[u].append(v) visited[v] = True q.append(v) siblings = [[] for _ in range(N)] for x in range(N): p = parent[x] if p == -1: continue siblings[x] = [child for child in children[p] if child != x] grandchildren = [[] for _ in range(N)] for x in range(N): gc = [] for child in children[x]: gc.extend(children[child]) grandchildren[x] = gc grandparent = [-1] * N for x in range(N): if parent[x] != -1: gp = parent[parent[x]] if gp != -1: grandparent[x] = gp A = list(map(int, input[ptr:ptr+N])) ptr += N Q = int(input[ptr]) ptr +=1 for _ in range(Q): x = int(input[ptr]) ptr +=1 nodes = set() nodes.add(x) p = parent[x] if p != -1: nodes.add(p) for child in children[x]: nodes.add(child) for sib in siblings[x]: nodes.add(sib) for gc in grandchildren[x]: nodes.add(gc) gp = grandparent[x] if gp != -1: nodes.add(gp) total = 0 for node in nodes: total += A[node] for node in nodes: A[node] = 0 A[x] = total print(total) if __name__ == "__main__": main()