結果

問題 No.1094 木登り / Climbing tree
ユーザー tanon710
提出日時 2020-07-08 01:12:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,316 ms / 2,000 ms
コード長 2,370 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 984 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 220,672 KB
最終ジャッジ日時 2024-11-08 06:58:59
合計ジャッジ時間 25,854 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

n=int(input())
edge=[list(map(int,input().split())) for _ in range(n-1)]
g=[[] for _ in range(n)]
for a,b,c in edge:
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))
par=[-1]*n
chi=[[] for _ in range(n)]
root=0
d=[0]*n
checked=[0]*n
checked[0]=1
q=collections.deque()
q.append(0)
while len(q)!=0:
    v=q.popleft()
    for u,w in g[v]:
        if checked[u]==0:
            checked[u]=1
            par[u]=v
            chi[v].append(u)
            d[u]=d[v]+w
            q.append(u)


N = 2*n-1
#RMQ - Indexed
def init_min(init_min_val):
    #set_val
    for i in range(N):
        seg_min[i+num_min-1]=init_min_val[i]*N + i    
    #built
    for i in range(num_min-2,-1,-1) :
        seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2]) 
    
def query_min(p,q):
    if q<=p:
        return ide_ele_min
    p += num_min-1
    q += num_min-2
    res=ide_ele_min
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg_min[p])
        if q&1 == 1:
            res = min(res,seg_min[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg_min[p])
    else:
        res = min(min(res,seg_min[p]),seg_min[q])
    return res


#####単位元######
ide_ele_min = 10**20

#num_min:N以上の最小の2のべき乗
num_min =2**(N-1).bit_length()
seg_min=[ide_ele_min]*2*num_min

#Euler Tour
tank = [root]
eulerTour = []
left = [0]*n
right = [-1]*n
depth = [-1]*n

eulerNum = -1
de = -1

while tank:
    q = tank.pop()
    if q >= 0:
        #first time
        eulerNum += 1
        eulerTour.append(q)
        left[q] = eulerNum
        right[q] = eulerNum
        tank.append(~q)
        de += 1
        depth[q] = de
        for ch in chi[q]:
            tank.append(ch)
    else:
        de -= 1
        if ~q != root:
            eulerTour.append(par[~q])
            eulerNum += 1
            right[par[~q]] = eulerNum
        
init_min([depth[e] for e in eulerTour])

def getLCM(u,v):
    g = query_min(min(left[u],left[v]),max(right[u],right[v])+1)
    return eulerTour[g%N]

q=int(input())
for _ in range(q):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    lca=getLCM(u,v)
    ans=d[u]+d[v]-2*d[lca]
    print(ans)
0