結果
問題 | No.1637 Easy Tree Query |
ユーザー |
|
提出日時 | 2021-08-06 21:52:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 503 ms / 2,000 ms |
コード長 | 1,149 bytes |
コンパイル時間 | 456 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 101,760 KB |
最終ジャッジ日時 | 2024-09-17 03:50:43 |
合計ジャッジ時間 | 11,741 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
# import sys # #sys.setrecursionlimit(1000000) # input = sys.stdin.readline def mp():return map(int,input().split()) def lmp():return list(map(int,input().split())) import math import bisect from copy import deepcopy as dc from itertools import accumulate from collections import Counter, defaultdict, deque import itertools def ceil(U,V):return (U+V-1)//V def modf1(N,MOD):return (N-1)%MOD+1 inf = int(1e30) mod = int(1e9+7) n,Q = mp() edge = [[] for i in range(n)] for i in range(n-1): a,b = mp() a -= 1 b -= 1 edge[a].append(b) edge[b].append(a) num = [[] for i in range(n)] num[0].append(0) kaisou = [0]*n q = deque([0]) used = [0]*n used[0] = 1 while q: here = q.popleft() for i in edge[here]: if not used[i]: used[i] += 1 kaisou[i] = kaisou[here] + 1 num[kaisou[i]].append(i) q.append(i) size = [1]*n for i in num[::-1]: for j in i: for k in edge[j]: if kaisou[j] - 1 == kaisou[k]: size[k] += size[j] # print(num) # print(size) ans = 0 for _ in range(Q): p,x = mp() p -= 1 ans += size[p]*x print(ans)