結果

問題 No.1094 木登り / Climbing tree
ユーザー tanon710tanon710
提出日時 2020-07-08 01:12:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,250 ms / 2,000 ms
コード長 2,370 bytes
コンパイル時間 295 ms
コンパイル使用メモリ 82,528 KB
実行使用メモリ 221,008 KB
最終ジャッジ日時 2024-04-25 19:21:03
合計ジャッジ時間 24,666 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
55,376 KB
testcase_01 AC 1,044 ms
202,820 KB
testcase_02 AC 338 ms
221,008 KB
testcase_03 AC 346 ms
85,572 KB
testcase_04 AC 457 ms
132,260 KB
testcase_05 AC 694 ms
186,112 KB
testcase_06 AC 597 ms
114,084 KB
testcase_07 AC 1,061 ms
186,760 KB
testcase_08 AC 1,056 ms
203,908 KB
testcase_09 AC 1,083 ms
203,508 KB
testcase_10 AC 1,044 ms
203,496 KB
testcase_11 AC 1,136 ms
202,912 KB
testcase_12 AC 1,021 ms
203,252 KB
testcase_13 AC 1,074 ms
203,100 KB
testcase_14 AC 1,038 ms
202,964 KB
testcase_15 AC 361 ms
107,788 KB
testcase_16 AC 559 ms
189,820 KB
testcase_17 AC 441 ms
141,536 KB
testcase_18 AC 405 ms
125,616 KB
testcase_19 AC 499 ms
166,804 KB
testcase_20 AC 1,250 ms
203,220 KB
testcase_21 AC 470 ms
146,260 KB
testcase_22 AC 1,033 ms
203,200 KB
testcase_23 AC 1,002 ms
199,788 KB
testcase_24 AC 1,028 ms
200,400 KB
testcase_25 AC 1,046 ms
198,200 KB
testcase_26 AC 1,005 ms
203,156 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