結果
問題 | No.1637 Easy Tree Query |
ユーザー |
![]() |
提出日時 | 2021-08-06 21:36:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 180 ms / 2,000 ms |
コード長 | 597 bytes |
コンパイル時間 | 279 ms |
コンパイル使用メモリ | 82,344 KB |
実行使用メモリ | 96,384 KB |
最終ジャッジ日時 | 2024-09-17 03:45:10 |
合計ジャッジ時間 | 6,592 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
import sys input = sys.stdin.readline N, Q = map(int, input().split()) e = [[] for _ in range(N + 1)] for _ in range(N - 1): u, v = map(int, input().split()) e[u].append(v) e[v].append(u) s = [1] vis = [0] * (N + 1) parent = [0] * (N + 1) vis[1] = 1 order = [] while len(s): x = s.pop() order.append(x) for y in e[x]: if vis[y]: continue parent[y] = x vis[y] = 1 s.append(y) size = [1] * (N + 1) order.reverse() for y in order[: -1]: x = parent[y] size[x] += size[y] res = 0 for _ in range(Q): x, v = map(int, input().split()) res += size[x] * v print(res)