結果

問題 No.898 tri-βutree
ユーザー neterukunneterukun
提出日時 2019-10-05 00:23:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,211 ms / 4,000 ms
コード長 3,110 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 149,376 KB
最終ジャッジ日時 2024-04-26 08:48:09
合計ジャッジ時間 20,683 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 485 ms
149,376 KB
testcase_01 AC 45 ms
54,272 KB
testcase_02 AC 59 ms
63,232 KB
testcase_03 AC 57 ms
62,720 KB
testcase_04 AC 56 ms
62,720 KB
testcase_05 AC 58 ms
62,976 KB
testcase_06 AC 57 ms
62,592 KB
testcase_07 AC 1,137 ms
145,932 KB
testcase_08 AC 1,139 ms
146,656 KB
testcase_09 AC 1,118 ms
146,696 KB
testcase_10 AC 1,166 ms
145,488 KB
testcase_11 AC 1,154 ms
146,372 KB
testcase_12 AC 1,201 ms
147,124 KB
testcase_13 AC 1,123 ms
146,720 KB
testcase_14 AC 1,211 ms
146,108 KB
testcase_15 AC 1,107 ms
146,268 KB
testcase_16 AC 1,143 ms
146,280 KB
testcase_17 AC 1,119 ms
146,360 KB
testcase_18 AC 1,120 ms
146,068 KB
testcase_19 AC 1,171 ms
146,476 KB
testcase_20 AC 1,158 ms
146,524 KB
testcase_21 AC 1,169 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):
    """重み付き根付き木に対して、根とそれぞれの頂点との距離を求める"""
    dist = [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:
                dist[child_v] = dist[v] + cost
                q.append((child_v, v))
    return dist


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)
dist= 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 = dist[u] + dist[v] - 2*dist[lca.lca(u, v)]
    vw = dist[v] + dist[w] - 2*dist[lca.lca(v, w)]
    wu = dist[w] + dist[u] - 2*dist[lca.lca(w, u)]
    print((uv+vw+wu)//2)
0