結果

問題 No.898 tri-βutree
ユーザー AEn
提出日時 2022-11-23 22:41:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,166 ms / 4,000 ms
コード長 2,224 bytes
コンパイル時間 381 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 198,400 KB
最終ジャッジ日時 2024-09-25 02:41:50
合計ジャッジ時間 20,633 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**8)
import pypyjit
pypyjit.set_param("max_unroll_recursion=-1")

class LCA:
    """
    前処理O(nlogn)、クエリO(logn)
    木上の任意の2点のLCAを求める
    """
    def __init__(self, N, G, root = 0) -> None:
        """頂点数:N、辺情報:G、根のidx:root dabulingで前処理を行う"""
        self.G = G
        self.depth = [-1]*N
        self.dist = [-1]*N
        self.ancestors = [[-1]*(N+1)]
        self.depth[root] = 0
        self.dist[root] = 0
        self.dfs(root,-1)
        max_d = max([self.depth[i] for i in range(N)])

        d = 1
        prev = self.ancestors[0]
        while d<max_d:
            nex = [prev[i] for i in prev]
            self.ancestors.append(nex)
            d <<= 1
            prev = nex

    def dfs(self,v,p):
        for nex, cost in self.G[v]:
            if nex==p:continue
            self.depth[nex] = self.depth[v]+1
            self.dist[nex] = self.dist[v]+cost
            self.ancestors[0][nex] = v
            self.dfs(nex,v)
    
    def lca_query(self, u, v):
        """u,vの最小共通祖先を求める"""
        du, dv = self.depth[u], self.depth[v]
        if du>dv:
            u, v = v, u
            du, dv = dv, du
        # vを同じ高さまで上げる
        diff, idx = dv-du, 0
        while diff:
            if diff&1:
                v = self.ancestors[idx][v]
            diff >>= 1
            idx += 1
        if u==v:
            return u
        for i in range(len(bin(du)[2:])-1,-1,-1):
            pu, pv = self.ancestors[i][u], self.ancestors[i][v]
            if pu!=pv:
                u, v = pu, pv
        assert self.ancestors[0][u]==self.ancestors[0][v]
        return self.ancestors[0][u]
    
    def dist_query(self, u, v):
        lca = self.lca_query(u, v)
        return self.dist[u]+self.dist[v]-2*self.dist[lca]

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

lca = LCA(N,G)
Q = int(input())
for i in range(Q):
    x, y, z = map(int, input().split())
    res = [lca.dist_query(x, y), lca.dist_query(y,z), lca.dist_query(z,x)]
    print(sum(res)//2)
0