結果

問題 No.1094 木登り / Climbing tree
ユーザー tanon710tanon710
提出日時 2020-07-08 01:12:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,316 ms / 2,000 ms
コード長 2,370 bytes
コンパイル時間 984 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 220,672 KB
最終ジャッジ日時 2024-11-08 06:58:59
合計ジャッジ時間 25,854 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
54,144 KB
testcase_01 AC 1,076 ms
203,008 KB
testcase_02 AC 383 ms
220,672 KB
testcase_03 AC 377 ms
85,200 KB
testcase_04 AC 537 ms
131,968 KB
testcase_05 AC 762 ms
186,112 KB
testcase_06 AC 590 ms
114,304 KB
testcase_07 AC 1,099 ms
186,752 KB
testcase_08 AC 1,079 ms
203,904 KB
testcase_09 AC 1,086 ms
203,008 KB
testcase_10 AC 1,081 ms
203,264 KB
testcase_11 AC 1,139 ms
202,880 KB
testcase_12 AC 1,159 ms
203,136 KB
testcase_13 AC 1,080 ms
203,264 KB
testcase_14 AC 1,117 ms
202,880 KB
testcase_15 AC 408 ms
107,648 KB
testcase_16 AC 598 ms
189,312 KB
testcase_17 AC 478 ms
141,440 KB
testcase_18 AC 436 ms
125,440 KB
testcase_19 AC 554 ms
166,784 KB
testcase_20 AC 1,316 ms
203,136 KB
testcase_21 AC 494 ms
145,792 KB
testcase_22 AC 1,073 ms
203,264 KB
testcase_23 AC 1,049 ms
199,484 KB
testcase_24 AC 1,065 ms
199,936 KB
testcase_25 AC 1,036 ms
198,140 KB
testcase_26 AC 1,070 ms
202,752 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/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