結果

問題 No.899 γatheree
ユーザー gew1fw
提出日時 2025-06-12 17:05:20
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,338 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 82,976 KB
実行使用メモリ 316,988 KB
最終ジャッジ日時 2025-06-12 17:05:37
合計ジャッジ時間 14,553 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        u = int(data[idx])
        v = int(data[idx+1])
        idx +=2
        edges[u].append(v)
        edges[v].append(u)

    A = list(map(int, data[idx:idx+N]))
    idx +=N

    Q = int(data[idx])
    idx +=1
    queries = []
    for _ in range(Q):
        x = int(data[idx])
        idx +=1
        queries.append(x)

    # Precompute for each node the list of nodes in S(x)
    S = [[] for _ in range(N)]
    for x in range(N):
        visited = set()
        q = deque()
        q.append( (x, 0) )
        visited.add(x)
        while q:
            u, d = q.popleft()
            if d > 2:
                continue
            S[x].append(u)
            for v in edges[u]:
                if v not in visited:
                    visited.add(v)
                    q.append( (v, d+1) )

    current_A = A.copy()
    for x in queries:
        total = 0
        for u in S[x]:
            total += current_A[u]
        current_A[x] = total
        for u in S[x]:
            if u != x:
                current_A[u] = 0
        print(total)

if __name__ == "__main__":
    main()
0