結果

問題 No.898 tri-βutree
コンテスト
ユーザー detteiuu
提出日時 2026-01-27 00:59:10
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 3,276 ms / 4,000 ms
コード長 3,294 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 306 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 149,980 KB
最終ジャッジ日時 2026-01-27 01:00:06
合計ジャッジ時間 52,881 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

class LCA:
    def __init__(self, G, root=0):
        V = len(G)
        self.bit_length = 1
        while 1<<self.bit_length < V:
            self.bit_length += 1
        self.parent = [[-1]*V for _ in range(self.bit_length)]
        self.depth = [-1]*V
        self.d = [-1]*V
        self.bfs(G, root)
        for i in range(self.bit_length-1):
            for j in range(V):
                if self.parent[i][j] != -1:
                    self.parent[i+1][j] = self.parent[i][self.parent[i][j]]
        
    def bfs(self, G, root):
        self.depth[root] = 0
        self.d[root] = 0
        que = deque()
        que.append(root)
        while que:
            n = que.popleft()
            for v, w in G[n]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[n]+w
                    self.d[v] = self.d[n]+1
                    self.parent[0][v] = n
                    que.append(v)
    
    def lca(self, a, b):
        if self.d[a] < self.d[b]:
            a, b = b, a
        for i in range(self.bit_length):
            if (self.d[a]-self.d[b]) & 1<<i:
                a = self.parent[i][a]
        if a == b:
            return a
        for i in reversed(range(self.bit_length)):
            if self.parent[i][a] != self.parent[i][b]:
                a = self.parent[i][a]
                b = self.parent[i][b]
        return self.parent[0][a]
    
    def dist(self, a, b):
        return self.depth[a]+self.depth[b]-self.depth[self.lca(a, b)]*2
    
    def is_ancestor(self, u, v):
        return self.lca(u, v) == u
    
    def kth_ancestor(self, n, k):
        for i in range(self.bit_length):
            if 1<<i & k:
                n = self.parent[i][n]
                if n == -1:
                    break
        return n
    
    def jump(self, u, v):
        if u == v:
            return u
        if self.lca(u, v) == u:
            return self.kth_ancestor(v, self.dist(u, v)-1)
        else:
            return self.parent[0][u]
    
    def jump_k(self, u, v, k):
        d = self.dist(u, v)
        if d <= k:
            return v
        lca = self.lca(u, v)
        if k <= self.depth[u]-self.depth[lca]:
            return self.kth_ancestor(u, k)
        else:
            return self.kth_ancestor(v, d-k)
    
    def on_path(self, u, v, x):
        return self.dist(u, x)+self.dist(x, v) == self.dist(u, v)

    def create_path(self, u, v, x):
        if self.on_path(u, v, x):
            return u, v
        if self.on_path(u, x, v):
            return u, x
        if self.on_path(v, x, u):
            return v, x
        return -1, -1

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]

lca = LCA(G)
for x, y, z in query:
    ans = lca.dist(x, y)
    l, r = lca.create_path(x, y, z)
    if l != -1:
        print(lca.dist(l, r))
        continue
    xy, xz, yz = lca.lca(x, y), lca.lca(x, z), lca.lca(y, z)
    if lca.depth[xz] < lca.depth[xy]:
        ans += lca.dist(xy, z)
    elif lca.depth[xz] < lca.depth[yz]:
        ans += lca.dist(yz, z)
    else:
        ans += lca.dist(xz, z)
    print(ans)
0