結果
問題 | No.898 tri-βutree |
ユーザー | titia |
提出日時 | 2019-10-04 23:13:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,671 ms / 4,000 ms |
コード長 | 2,438 bytes |
コンパイル時間 | 323 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 163,120 KB |
最終ジャッジ日時 | 2024-04-26 08:43:41 |
合計ジャッジ時間 | 28,278 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 549 ms
127,424 KB |
testcase_01 | AC | 42 ms
54,656 KB |
testcase_02 | AC | 56 ms
65,408 KB |
testcase_03 | AC | 55 ms
65,792 KB |
testcase_04 | AC | 56 ms
65,792 KB |
testcase_05 | AC | 55 ms
65,408 KB |
testcase_06 | AC | 60 ms
65,792 KB |
testcase_07 | AC | 1,185 ms
127,072 KB |
testcase_08 | AC | 2,622 ms
163,120 KB |
testcase_09 | AC | 2,615 ms
161,368 KB |
testcase_10 | AC | 1,198 ms
126,900 KB |
testcase_11 | AC | 1,184 ms
126,768 KB |
testcase_12 | AC | 1,151 ms
127,220 KB |
testcase_13 | AC | 1,134 ms
125,424 KB |
testcase_14 | AC | 2,671 ms
161,696 KB |
testcase_15 | AC | 1,154 ms
129,000 KB |
testcase_16 | AC | 1,097 ms
127,484 KB |
testcase_17 | AC | 2,619 ms
162,056 KB |
testcase_18 | AC | 1,187 ms
128,708 KB |
testcase_19 | AC | 1,125 ms
127,196 KB |
testcase_20 | AC | 1,100 ms
126,848 KB |
testcase_21 | AC | 2,635 ms
160,444 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)