結果
問題 | No.1637 Easy Tree Query |
ユーザー | kyaneko999 |
提出日時 | 2021-08-06 21:29:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 312 ms / 2,000 ms |
コード長 | 3,493 bytes |
コンパイル時間 | 1,497 ms |
コンパイル使用メモリ | 81,580 KB |
実行使用メモリ | 107,324 KB |
最終ジャッジ日時 | 2023-10-17 04:56:27 |
合計ジャッジ時間 | 10,468 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 56 ms
65,984 KB |
testcase_01 | AC | 56 ms
65,984 KB |
testcase_02 | AC | 226 ms
104,172 KB |
testcase_03 | AC | 56 ms
66,016 KB |
testcase_04 | AC | 194 ms
91,632 KB |
testcase_05 | AC | 194 ms
87,788 KB |
testcase_06 | AC | 169 ms
84,584 KB |
testcase_07 | AC | 117 ms
78,376 KB |
testcase_08 | AC | 168 ms
87,176 KB |
testcase_09 | AC | 263 ms
99,096 KB |
testcase_10 | AC | 150 ms
83,168 KB |
testcase_11 | AC | 282 ms
101,832 KB |
testcase_12 | AC | 251 ms
94,724 KB |
testcase_13 | AC | 138 ms
83,508 KB |
testcase_14 | AC | 254 ms
99,376 KB |
testcase_15 | AC | 296 ms
101,236 KB |
testcase_16 | AC | 296 ms
100,600 KB |
testcase_17 | AC | 148 ms
83,296 KB |
testcase_18 | AC | 198 ms
87,796 KB |
testcase_19 | AC | 210 ms
89,828 KB |
testcase_20 | AC | 246 ms
94,440 KB |
testcase_21 | AC | 192 ms
92,080 KB |
testcase_22 | AC | 307 ms
101,700 KB |
testcase_23 | AC | 154 ms
84,840 KB |
testcase_24 | AC | 193 ms
91,928 KB |
testcase_25 | AC | 185 ms
85,732 KB |
testcase_26 | AC | 252 ms
95,044 KB |
testcase_27 | AC | 312 ms
103,532 KB |
testcase_28 | AC | 178 ms
85,760 KB |
testcase_29 | AC | 223 ms
93,652 KB |
testcase_30 | AC | 188 ms
93,404 KB |
testcase_31 | AC | 113 ms
77,548 KB |
testcase_32 | AC | 171 ms
87,084 KB |
testcase_33 | AC | 175 ms
83,276 KB |
testcase_34 | AC | 154 ms
107,324 KB |
ソースコード
from sys import exit, stdin, setrecursionlimit from collections import deque, defaultdict, Counter from copy import deepcopy from bisect import bisect_left, bisect_right, insort_left, insort_right from heapq import heapify, heappop, heappush from itertools import product, permutations, combinations, combinations_with_replacement from functools import reduce from math import gcd, sin, cos, tan, asin, acos, atan, atan2, degrees, radians, ceil, floor, sqrt, factorial from math import pi as PI from random import randint as rd setrecursionlimit(500000) INF = (1<<61)-1 EPS = 1e-10 MOD = 10**9+7 # MOD = 998244353 def input(): return stdin.readline().strip('\n') def intput(): return int(input()) def minput(): return input().split() def linput(): return input().split() def mint(): return map(int,input().split()) def lint(): return list(map(int,input().split())) def ilint(): return intput(),lint() def lcm(x,y): return x*y//gcd(x,y) def lgcd(l): return reduce(gcd,l) def llcm(l): return reduce(lcm,l) def powmod(n,i,mod=MOD): return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod) def div2(x): return x.bit_length() def div10(x): return len(str(x))-(x==0) def popcount(x): return bin(x).count('1') def digit(x,i,max_len=None): s = str(x) if max_len: i -= max_len-len(s) return int(s[i-1]) if i>0 else 0 def digitsum(x): ans = 0 for i in range(div10(x)): ans += digit(x,i+1) return ans def pf(x,mode='counter'): C = Counter() p = 2 while x>1: k = 0 while x%p==0: x //= p k += 1 if k>0: C[p] += k p = p+2-(p==2) if p*p<x else x if mode=='counter': return C S = set([1]) for k in C: T = set() for x in S: for i in range(C[k]+1): T.add(x*(k**i)) S = T if mode=='set': return S if mode=='list': return sorted(S) def isprime(x): if x<2: return False return len(pf(x,'set'))==2 def matmul(A, B): # import numpy A1, A2 = A >> 15, A & (1 << 15) - 1 B1, B2 = B >> 15, B & (1 << 15) - 1 X = np.dot(A1, B1) % MOD Y = np.dot(A2, B2) Z = np.dot(A1 + A2, B1 + B2) - X - Y return ((X << 30) + (Z << 15) + Y) % MOD def matpow(A, N): P = np.eye(A.shape[0], dtype=np.int64) while N: if N & 1: P = matmul(P, A) A = matmul(A, A) N >>= 1 return P def zash(S): lis = sorted(S) dic = {} for i,x in enumerate(lis): dic[x] = i return lis, dic def pr(*x): print(*x, sep='', end='') if len(x) else print() def lprint(l): for x in l: print(x) def ston(c, c0='a'): return ord(c)-ord(c0) def ntos(x, c0='a'): return chr(x+ord(c0)) def judge(x, l=['Yes', 'No']): print(l[0] if x else l[1]) def debug(*x, flag=1): if flag: print(*x) ###################################################### N,Q=mint() node=[[] for _ in range(N+1)] for _ in range(N-1): x,y=mint() node[x].append(y) node[y].append(x) order=[] done=[0]*(N+1) kids=[[] for _ in range(N+1)] q=deque() q.append(1) done[1]=1 while q: x=q.popleft() order.append(x) for y in node[x]: if not done[y]: q.append(y) done[y]=1 kids[x].append(y) cnt=[1]*(N+1) for x in order[::-1]: for y in kids[x]: cnt[x]+=cnt[y] S=0 for _ in range(Q): p,x=mint() S+=x*cnt[p] print(S)