結果
問題 | No.1094 木登り / Climbing tree |
ユーザー | takakin |
提出日時 | 2020-07-25 21:26:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,085 ms / 2,000 ms |
コード長 | 1,304 bytes |
コンパイル時間 | 356 ms |
コンパイル使用メモリ | 82,664 KB |
実行使用メモリ | 145,024 KB |
最終ジャッジ日時 | 2024-04-25 19:22:00 |
合計ジャッジ時間 | 23,293 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
52,608 KB |
testcase_01 | AC | 930 ms
144,516 KB |
testcase_02 | AC | 245 ms
142,376 KB |
testcase_03 | AC | 224 ms
81,832 KB |
testcase_04 | AC | 335 ms
106,168 KB |
testcase_05 | AC | 515 ms
134,964 KB |
testcase_06 | AC | 443 ms
98,148 KB |
testcase_07 | AC | 1,027 ms
143,844 KB |
testcase_08 | AC | 1,043 ms
143,816 KB |
testcase_09 | AC | 936 ms
143,700 KB |
testcase_10 | AC | 1,042 ms
143,784 KB |
testcase_11 | AC | 1,026 ms
144,416 KB |
testcase_12 | AC | 934 ms
143,784 KB |
testcase_13 | AC | 1,085 ms
144,172 KB |
testcase_14 | AC | 1,057 ms
143,636 KB |
testcase_15 | AC | 297 ms
91,480 KB |
testcase_16 | AC | 528 ms
128,132 KB |
testcase_17 | AC | 403 ms
106,564 KB |
testcase_18 | AC | 374 ms
100,244 KB |
testcase_19 | AC | 485 ms
118,732 KB |
testcase_20 | AC | 938 ms
143,792 KB |
testcase_21 | AC | 422 ms
109,008 KB |
testcase_22 | AC | 1,036 ms
143,916 KB |
testcase_23 | AC | 907 ms
144,260 KB |
testcase_24 | AC | 1,027 ms
145,024 KB |
testcase_25 | AC | 910 ms
144,392 KB |
testcase_26 | AC | 937 ms
144,644 KB |
ソースコード
import sys input=lambda: sys.stdin.readline().rstrip() n=int(input()) Edge=[[] for i in range(n)] for i in range(n-1): a,b,c=map(int,input().split()) Edge[a-1].append((c,b-1)) Edge[b-1].append((c,a-1)) inf=float("inf") prv=[inf]*n #各頂点の親 prv[0]=-1 depth=[inf]*n #深さ depth[0]=0 stack=[0] while stack: cur=stack.pop() for w,next in Edge[cur]: if prv[next]==inf: prv[next]=cur depth[next]=depth[cur]+1 stack.append(next) #LCA LV=(n-1).bit_length() #n=頂点数 def construct(prv): kprv=[prv] S=prv for k in range(LV): T=[0]*n for i in range(n): if S[i] is None: continue T[i]=S[S[i]] kprv.append(T) S=T return kprv kprv=construct(prv) # kprv[k][u]=v: 頂点uの2^k個上の祖先頂点v def lca(u,v,kprv,depth): dd=depth[v]-depth[u] if dd<0: u,v=v,u dd=-dd for k in range(LV+1): if dd&1: v=kprv[k][v] dd>>=1 if u==v: return u for k in range(LV-1,-1,-1): pu,pv=kprv[k][u],kprv[k][v] if pu!=pv: u,v=pu,pv return kprv[0][u] D=[inf]*n D[0]=0 S=[0] while S: next=S.pop() for w,g in Edge[next]: if D[g]==inf: D[g]=D[next]+w S.append(g) q=int(input()) for _ in range(q): s,t=map(int,input().split()) print(D[s-1]+D[t-1]-2*D[lca(s-1,t-1,kprv,depth)])