結果
問題 | No.898 tri-βutree |
ユーザー | titia |
提出日時 | 2019-10-04 23:13:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,807 ms / 4,000 ms |
コード長 | 2,438 bytes |
コンパイル時間 | 1,632 ms |
コンパイル使用メモリ | 86,692 KB |
実行使用メモリ | 174,836 KB |
最終ジャッジ日時 | 2023-08-08 16:06:28 |
合計ジャッジ時間 | 31,504 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 589 ms
132,752 KB |
testcase_01 | AC | 90 ms
71,552 KB |
testcase_02 | AC | 105 ms
76,216 KB |
testcase_03 | AC | 105 ms
76,332 KB |
testcase_04 | AC | 104 ms
76,560 KB |
testcase_05 | AC | 104 ms
76,508 KB |
testcase_06 | AC | 105 ms
76,216 KB |
testcase_07 | AC | 1,188 ms
127,228 KB |
testcase_08 | AC | 2,768 ms
168,028 KB |
testcase_09 | AC | 2,743 ms
174,836 KB |
testcase_10 | AC | 1,198 ms
128,912 KB |
testcase_11 | AC | 1,201 ms
127,712 KB |
testcase_12 | AC | 1,199 ms
127,592 KB |
testcase_13 | AC | 1,202 ms
127,128 KB |
testcase_14 | AC | 2,689 ms
172,144 KB |
testcase_15 | AC | 1,228 ms
129,716 KB |
testcase_16 | AC | 1,176 ms
127,928 KB |
testcase_17 | AC | 2,669 ms
172,032 KB |
testcase_18 | AC | 1,209 ms
129,224 KB |
testcase_19 | AC | 1,160 ms
127,184 KB |
testcase_20 | AC | 1,170 ms
127,984 KB |
testcase_21 | AC | 2,807 ms
170,316 KB |
ソースコード
import sys input = sys.stdin.readline N=int(input()) EDGE=[list(map(int,input().split())) for i in range(N-1)] EDGELIST=[[] for i in range(N)] for x,y,l in EDGE: EDGELIST[x].append((y,l)) EDGELIST[y].append((x,l)) # LCA(オイラーツアー+Segment tree) DEPTH=[-1]*N DEPTH[0]=0 from collections import deque QUE = deque([0]) QUE2 = deque() EULER=[]# (i,j)で,(1からツアーで辿った点の深さ,そのindex) USED=[0]*N while QUE: x=QUE.pop() EULER.append((DEPTH[x],x)) if USED[x]==1: continue for to,l in EDGELIST[x]: if USED[to]==0: DEPTH[to]=DEPTH[x]+1 QUE2.append(to) else: QUE.append(to) QUE.extend(QUE2) QUE2=deque() USED[x]=1 MINP=[1<<30]*N MAXP=[-1]*N for ind,(depth,p) in enumerate(EULER): MINP[p]=min(MINP[p],ind) MAXP[p]=max(MAXP[p],ind) LEN=len(EULER) seg_el=1<<(LEN.bit_length())# Segment treeの台の要素数 SEG=[(1<<30,0)]*(2*seg_el)# 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化 for i in range(LEN):# Dを対応する箇所へupdate SEG[i+seg_el]=EULER[i] for i in range(seg_el-1,0,-1):# 親の部分もupdate SEG[i]=min(SEG[i*2],SEG[i*2+1]) def update(n,x,seg_el):# A[n]をxへ更新(反映) i=n+seg_el SEG[i]=x i>>=1# 子ノードへ while i!=0: SEG[i]=min(SEG[i*2],SEG[i*2+1]) i>>=1 def getvalues(l,r):# 区間[l,r)に関するminを調べる L=l+seg_el R=r+seg_el ANS=(1<<30,0) while L<R: if L & 1: ANS=min(ANS , SEG[L]) L+=1 if R & 1: R-=1 ANS=min(ANS , SEG[R]) L>>=1 R>>=1 return ANS def LCA(l,r): return getvalues(min(MINP[l],MINP[r]),max(MAXP[l],MAXP[r])+1) Q = deque([0]) DLENGTH=[0]*N USE=[0]*N USE[0]=1 while Q: x=Q.pop() for to,l in EDGELIST[x]: if USE[to]==0: Q.append(to) USE[to]=1 DLENGTH[to]=DLENGTH[x]+l #print(DLENGTH) Query=int(input()) def plusxy(x,y,ANS): if LCA(x,y) in {x,y}: ANS+=abs(DLENGTH[x]-DLENGTH[y]) else: ANS+=DLENGTH[x]+DLENGTH[y]-2*DLENGTH[LCA(x,y)[1]] return ANS for testcases in range(Query): x,y,z=map(int,(input().split())) ANS=0 ANS=plusxy(x,y,ANS) ANS=plusxy(y,z,ANS) ANS=plusxy(z,x,ANS) print(ANS//2)