結果

問題 No.898 tri-βutree
ユーザー kohei2019kohei2019
提出日時 2022-08-01 23:15:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,799 ms / 4,000 ms
コード長 2,937 bytes
コンパイル時間 474 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 134,864 KB
最終ジャッジ日時 2024-07-22 14:07:17
合計ジャッジ時間 16,946 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 370 ms
119,216 KB
testcase_01 AC 36 ms
53,784 KB
testcase_02 AC 48 ms
61,808 KB
testcase_03 AC 45 ms
60,688 KB
testcase_04 AC 44 ms
62,192 KB
testcase_05 AC 44 ms
62,476 KB
testcase_06 AC 43 ms
61,792 KB
testcase_07 AC 763 ms
113,336 KB
testcase_08 AC 1,799 ms
134,864 KB
testcase_09 AC 766 ms
112,776 KB
testcase_10 AC 758 ms
112,504 KB
testcase_11 AC 763 ms
112,580 KB
testcase_12 AC 816 ms
113,748 KB
testcase_13 AC 787 ms
113,128 KB
testcase_14 AC 796 ms
112,544 KB
testcase_15 AC 793 ms
112,368 KB
testcase_16 AC 771 ms
112,868 KB
testcase_17 AC 1,530 ms
127,672 KB
testcase_18 AC 809 ms
112,692 KB
testcase_19 AC 810 ms
112,596 KB
testcase_20 AC 823 ms
113,380 KB
testcase_21 AC 837 ms
113,444 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#最小共通祖先
#ダブリング
class LcaDoubling:
    """
    links[v] = { (u, w), (u, w), ... }  (u:隣接頂点, w:辺の重み)
    というグラフ情報から、ダブリングによるLCAを構築。
    任意の2頂点のLCAおよび距離を取得できるようにする
    """
 
    def __init__(self, n, links, root=0):
        self.depths = [-1] * n
        self.distances = [-1] * n
        prev_ancestors = self._init_dfs(n, links, root)
        self.ancestors = [prev_ancestors]
        max_depth = max(self.depths)
        d = 1
        while d < max_depth:
            next_ancestors = [prev_ancestors[p] for p in prev_ancestors]
            self.ancestors.append(next_ancestors)
            d <<= 1
            prev_ancestors = next_ancestors
 
    def _init_dfs(self, n, links, root):
        q = [(root, -1, 0, 0)]
        direct_ancestors = [-1] * (n + 1)  # 頂点数より1個長くし、存在しないことを-1で表す。末尾(-1)要素は常に-1
        while q:
            v, p, dep, dist = q.pop()
            direct_ancestors[v] = p
            self.depths[v] = dep
            self.distances[v] = dist
            q.extend((u, v, dep + 1, dist + w) for u, w in links[v] if u != p)
        return direct_ancestors
 
    def get_lca(self, u, v):
        du, dv = self.depths[u], self.depths[v]
        if du > dv:
            u, v = v, u
            du, dv = dv, du
        tu = u
        tv = self.upstream(v, dv - du)
        if u == tv:
            return u
        for k in range(du.bit_length() - 1, -1, -1):
            mu = self.ancestors[k][tu]
            mv = self.ancestors[k][tv]
            if mu != mv:
                tu = mu
                tv = mv
        lca = self.ancestors[0][tu]
        assert lca == self.ancestors[0][tv]
        return lca
 
    def get_distance(self, u, v):
        lca = self.get_lca(u, v)
        return self.distances[u] + self.distances[v] - 2 * self.distances[lca]
 
    def upstream(self, v, k):
        i = 0
        while k:
            if k & 1:
                v = self.ancestors[i][v]
            k >>= 1
            i += 1
        return v
 
N = int(input())
links = [[] for i in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    links[u].append((v,w))
    links[v].append((u,w))
LCA = LcaDoubling(N, links)
Q = int(input())
ans = []
for i in range(Q):
    x,y,z = map(int,input().split())
    a = LCA.get_lca(x, y)
    b = LCA.get_lca(y, z)
    c = LCA.get_lca(z, x)
    if a == b == c:
        dist = LCA.get_distance(0,x)+LCA.get_distance(0,y)+LCA.get_distance(0,z)-3*LCA.get_distance(0,a)
        
    else:
        l = [a,b,c]
        l.sort()
        r2 = l[1]
        for i in range(3):
            if l[i] != r2:
                r1 = l[i]
        dist = LCA.get_distance(0,x)+LCA.get_distance(0,y)+LCA.get_distance(0,z)-2*LCA.get_distance(0,r2)-LCA.get_distance(0,r1)
    ans.append(dist)
print(*ans,sep='\n')
0