結果

問題 No.898 tri-βutree
ユーザー AEnAEn
提出日時 2022-11-23 22:41:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,229 ms / 4,000 ms
コード長 2,224 bytes
コンパイル時間 1,355 ms
コンパイル使用メモリ 81,548 KB
実行使用メモリ 199,072 KB
最終ジャッジ日時 2023-10-25 07:22:50
合計ジャッジ時間 22,266 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 867 ms
199,072 KB
testcase_01 AC 39 ms
53,556 KB
testcase_02 AC 44 ms
55,604 KB
testcase_03 AC 44 ms
55,608 KB
testcase_04 AC 44 ms
55,608 KB
testcase_05 AC 44 ms
55,604 KB
testcase_06 AC 43 ms
55,608 KB
testcase_07 AC 1,229 ms
101,400 KB
testcase_08 AC 1,176 ms
101,280 KB
testcase_09 AC 1,218 ms
101,376 KB
testcase_10 AC 1,172 ms
101,300 KB
testcase_11 AC 1,174 ms
101,440 KB
testcase_12 AC 1,182 ms
101,476 KB
testcase_13 AC 1,161 ms
101,468 KB
testcase_14 AC 1,162 ms
101,048 KB
testcase_15 AC 1,196 ms
101,132 KB
testcase_16 AC 1,180 ms
101,504 KB
testcase_17 AC 1,169 ms
101,040 KB
testcase_18 AC 1,203 ms
100,556 KB
testcase_19 AC 1,174 ms
101,108 KB
testcase_20 AC 1,220 ms
101,056 KB
testcase_21 AC 1,189 ms
101,380 KB
権限があれば一括ダウンロードができます

ソースコード

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