結果

問題 No.898 tri-βutree
ユーザー titiatitia
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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-indexed2*seg_el.Segment tree
for i in range(LEN):# Dupdate
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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0