結果

問題 No.898 tri-βutree
ユーザー neterukunneterukun
提出日時 2019-10-04 21:41:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,162 ms / 4,000 ms
コード長 3,067 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 150,016 KB
最終ジャッジ日時 2024-11-08 22:00:35
合計ジャッジ時間 20,260 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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):
    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