結果

問題 No.898 tri-βutree
コンテスト
ユーザー neterukun
提出日時 2019-10-05 00:23:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,232 ms / 4,000 ms
コード長 3,110 bytes
コンパイル時間 225 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 149,956 KB
最終ジャッジ日時 2024-11-08 22:39:32
合計ジャッジ時間 21,356 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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