結果

問題 No.899 γatheree
ユーザー qwewe
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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()
0