結果

問題 No.898 tri-βutree
ユーザー neterukunneterukun
提出日時 2019-10-04 21:41:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,304 ms / 4,000 ms
コード長 3,067 bytes
コンパイル時間 965 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 149,760 KB
最終ジャッジ日時 2024-04-26 08:31:25
合計ジャッジ時間 21,688 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 477 ms
149,760 KB
testcase_01 AC 44 ms
54,272 KB
testcase_02 AC 60 ms
63,360 KB
testcase_03 AC 58 ms
62,720 KB
testcase_04 AC 57 ms
62,592 KB
testcase_05 AC 56 ms
62,720 KB
testcase_06 AC 59 ms
62,848 KB
testcase_07 AC 1,158 ms
145,932 KB
testcase_08 AC 1,117 ms
146,528 KB
testcase_09 AC 1,157 ms
146,280 KB
testcase_10 AC 1,134 ms
145,752 KB
testcase_11 AC 1,139 ms
146,384 KB
testcase_12 AC 1,158 ms
146,972 KB
testcase_13 AC 1,085 ms
146,752 KB
testcase_14 AC 1,144 ms
146,160 KB
testcase_15 AC 1,135 ms
146,012 KB
testcase_16 AC 1,128 ms
145,892 KB
testcase_17 AC 1,142 ms
145,980 KB
testcase_18 AC 1,127 ms
146,200 KB
testcase_19 AC 1,304 ms
146,472 KB
testcase_20 AC 1,247 ms
146,320 KB
testcase_21 AC 1,161 ms
145,444 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque


class LowestCommonAncestor():
    """根付き木に対して、二頂点の共通の祖先で最も近いところにある頂点を求める
    初期化(ダブリング配列parent[k][v]の構築): O(NlogN)
    lcaを求めるクエリ: O(logN)
    """
    
    def __init__(self, tree, root):
        self.n = len(tree)
        self.depth = [0] * self.n
        self.log_size = (self.n).bit_length()
        self.parent = [[-1] * self.n for i in range(self.log_size)]

        # 親を2^0回たどって到達する頂点、つまり現在の頂点に対する親の頂点を求める
        # parent[0][現在の頂点] = 親の頂点
        q = deque([(root, -1, 0)]) # (現在の地点, 親の頂点, 現在の頂点と親の頂点間の距離) 
        while q:
            v, par, dist = q.pop()
            self.parent[0][v] = par
            self.depth[v] = dist
            for child_v in tree[v]:
                if child_v != par:
                    self.depth[child_v] = dist + 1
                    q.append((child_v, v, dist + 1))

        # ダブリングで親を2^k回たどって到達する頂点を求める
        for k in range(1, self.log_size):
            for v in range(self.n):
                self.parent[k][v] = self.parent[k-1][self.parent[k-1][v]]
            
    def lca(self, u, v):
        # u, vのうち深いところにある方から|depth[u] - depth[v]|だけ親をたどる
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        for k in range(self.log_size):
            if (self.depth[v] - self.depth[u] >> k) & 1:
                v = self.parent[k][v]
        if u == v:
            return u
          
        # 二分探索でLCAを求める
        for k in reversed(range(self.log_size)):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]


def distance(tree_with_cost, root):
    dist2 = [0] * len(tree_with_cost)
    
    # 根からの距離を求める
    q = deque([(root, -1)]) # (現在の地点, 親の頂点) 
    while q:
        v, par = q.pop()
        for child_v, cost in tree_with_cost[v]:
            if child_v != par:
                dist2[child_v] = dist2[v] + cost
                q.append((child_v, v))
    return dist2


n = int(input())
info = [list(map(int, input().split())) for i in range(n-1)]
tree = [[] for i in range(n)]
tree_with_cost = [[] for i in range(n)]
for i in range(n-1):
    a, b, cost = info[i]
    tree[a].append(b)
    tree[b].append(a)
    tree_with_cost[a].append((b, cost))
    tree_with_cost[b].append((a, cost))

lca = LowestCommonAncestor(tree, 0)
kyori = distance(tree_with_cost, 0)

q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    u, v, w = query[i]
    uv = kyori[u] + kyori[v] - 2* kyori[lca.lca(u, v)]
    vw = kyori[v] + kyori[w] - 2* kyori[lca.lca(v, w)]
    wu = kyori[w] + kyori[u] - 2* kyori[lca.lca(w, u)]
    print((uv+vw+wu)//2)
0