結果
問題 | No.898 tri-βutree |
ユーザー |
![]() |
提出日時 | 2019-10-04 23:13:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,928 ms / 4,000 ms |
コード長 | 2,438 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 162,652 KB |
最終ジャッジ日時 | 2024-11-08 22:26:48 |
合計ジャッジ時間 | 31,115 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
import sysinput = sys.stdin.readlineN=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]*NDEPTH[0]=0from collections import dequeQUE = deque([0])QUE2 = deque()EULER=[]# (i,j)で,(1からツアーで辿った点の深さ,そのindex)USED=[0]*Nwhile QUE:x=QUE.pop()EULER.append((DEPTH[x],x))if USED[x]==1:continuefor to,l in EDGELIST[x]:if USED[to]==0:DEPTH[to]=DEPTH[x]+1QUE2.append(to)else:QUE.append(to)QUE.extend(QUE2)QUE2=deque()USED[x]=1MINP=[1<<30]*NMAXP=[-1]*Nfor 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を対応する箇所へupdateSEG[i+seg_el]=EULER[i]for i in range(seg_el-1,0,-1):# 親の部分もupdateSEG[i]=min(SEG[i*2],SEG[i*2+1])def update(n,x,seg_el):# A[n]をxへ更新(反映)i=n+seg_elSEG[i]=xi>>=1# 子ノードへwhile i!=0:SEG[i]=min(SEG[i*2],SEG[i*2+1])i>>=1def getvalues(l,r):# 区間[l,r)に関するminを調べるL=l+seg_elR=r+seg_elANS=(1<<30,0)while L<R:if L & 1:ANS=min(ANS , SEG[L])L+=1if R & 1:R-=1ANS=min(ANS , SEG[R])L>>=1R>>=1return ANSdef LCA(l,r):return getvalues(min(MINP[l],MINP[r]),max(MAXP[l],MAXP[r])+1)Q = deque([0])DLENGTH=[0]*NUSE=[0]*NUSE[0]=1while Q:x=Q.pop()for to,l in EDGELIST[x]:if USE[to]==0:Q.append(to)USE[to]=1DLENGTH[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 ANSfor testcases in range(Query):x,y,z=map(int,(input().split()))ANS=0ANS=plusxy(x,y,ANS)ANS=plusxy(y,z,ANS)ANS=plusxy(z,x,ANS)print(ANS//2)