結果
問題 | No.1098 LCAs |
ユーザー | 👑 Kazun |
提出日時 | 2020-06-26 23:25:11 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,016 bytes |
コンパイル時間 | 265 ms |
コンパイル使用メモリ | 86,952 KB |
実行使用メモリ | 234,516 KB |
最終ジャッジ日時 | 2023-09-18 08:08:47 |
合計ジャッジ時間 | 19,733 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 108 ms
72,424 KB |
testcase_01 | AC | 105 ms
72,316 KB |
testcase_02 | AC | 106 ms
72,580 KB |
testcase_03 | AC | 106 ms
72,428 KB |
testcase_04 | AC | 109 ms
72,320 KB |
testcase_05 | AC | 110 ms
72,268 KB |
testcase_06 | AC | 109 ms
72,436 KB |
testcase_07 | AC | 110 ms
72,516 KB |
testcase_08 | AC | 107 ms
72,452 KB |
testcase_09 | AC | 108 ms
72,440 KB |
testcase_10 | AC | 107 ms
72,220 KB |
testcase_11 | AC | 107 ms
72,424 KB |
testcase_12 | AC | 107 ms
72,340 KB |
testcase_13 | AC | 153 ms
78,612 KB |
testcase_14 | AC | 154 ms
78,596 KB |
testcase_15 | AC | 157 ms
78,692 KB |
testcase_16 | AC | 160 ms
79,240 KB |
testcase_17 | AC | 156 ms
78,888 KB |
testcase_18 | AC | 1,665 ms
234,516 KB |
testcase_19 | AC | 1,754 ms
228,572 KB |
testcase_20 | AC | 1,613 ms
225,868 KB |
testcase_21 | AC | 1,627 ms
227,252 KB |
testcase_22 | AC | 1,827 ms
230,424 KB |
testcase_23 | AC | 876 ms
172,912 KB |
testcase_24 | AC | 803 ms
172,808 KB |
testcase_25 | AC | 606 ms
163,992 KB |
testcase_26 | AC | 741 ms
220,444 KB |
testcase_27 | AC | 738 ms
212,040 KB |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
ソースコード
from functools import lru_cache from collections import deque N=int(input()) E={i:[] for i in range(1,N+1)} for _ in range(N-1): u,v=map(int,input().split()) E[u].append(v) E[v].append(u) T=[None]*(N+1) U=[False]*(N+1) F=[[] for _ in range(N+1)] Q=deque() T[1]=0 Q.append(1) while Q: v=Q.popleft() G=True for u in E[v]: if T[u]==None: Q.append(u) F[v].append(u) T[u]=1 G=False if G: U[v]=True @lru_cache(maxsize=2*10**5) def f(N): if U[N]: return 1 else: T=1 for v in F[N]: T+=f(v) return T def h(L): S=0 for p in L: S+=p*p T=sum(L) return T*T-S @lru_cache(maxsize=2*10**5+100) def g(N): if U[N]: return 1 else: C=[] for v in F[N]: C.append(f(v)) return h(C)+2*sum(C)+1 Z=[0]*(N+1) for i in range(2,N+1): Z[i]=g(i) Z[1]=N*N-sum(Z[2:]) for i in range(1,N+1): print(Z[i])