結果

問題 No.898 tri-βutree
コンテスト
ユーザー 双六
提出日時 2019-10-05 10:46:12
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 2,996 ms / 4,000 ms
コード長 2,278 bytes
コンパイル時間 225 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 69,312 KB
最終ジャッジ日時 2024-10-05 08:38:56
合計ジャッジ時間 49,912 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.buffer.readline
import queue
from collections import defaultdict

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, N):
		#初期化
		self.g = graph.graph
		self.Q = queue.Queue()
		self.depth = [INF] * N
		self.depth[0] = 0
		self.prev = [None] * N
		self.prev[0] = -1
		self.visit = [0] * N
		self.visit[0] = 1
		self.dist = [INF] * N
		self.dist[0] = 0

		#深さ、距離、親確定
		self.Q.put(0)
		while not self.Q.empty():
			v = self.Q.get()
			for i, w in self.g[v]:
				if self.visit[i] == 0:
					self.depth[i] = self.depth[v] + 1
					self.dist[i] = self.dist[v] + w
					self.Q.put(i)
					self.visit[i] = 1
					self.prev[i] = v

		#ダブリング
		self.nex = [[0] * N for i in range(N.bit_length())]
		for i in range(N):
			self.nex[0][i] = self.prev[i]
		for i in range(1, N.bit_length()):
			for j in range(N):
				if self.nex[i - 1][j] == -1:
					self.nex[i][j] = -1
				else:
					self.nex[i][j] = self.nex[i - 1][self.nex[i - 1][j]]

#入力
G = Graph()
N = int(input())
for i in range(N - 1):
	a, b, w = getlist()
	G.add_edge(a, b, w)
	G.add_edge(b, a, w)

bfs = BFS(G, N)
depth = bfs.depth
nex = bfs.nex
dist = bfs.dist

def LCA(a, b, N):
	x, y = a, b
	#深さ揃え
	if depth[x] > depth[y]:
		n = depth[x] - depth[y]
		X = n.bit_length()
		for i in range(X):
			if n & 1 == 1:
				x = nex[i][x]
			n = n >> 1
	elif depth[x] < depth[y]:
		n = depth[y] - depth[x]
		X = n.bit_length()
		for i in range(X):
			if n & 1 == 1:
				y = nex[i][y]
			n  = n >> 1
	if x == y:
		lca = x
		return lca
	#LCA計算
	for i in range(N.bit_length()):
		if nex[N.bit_length() - 1 - i][x] != nex[N.bit_length() - 1 - i][y]:
			x = nex[N.bit_length() - 1 - i][x]
			y = nex[N.bit_length() - 1 - i][y]
	lca = nex[0][x]
	return lca

Q = int(input())
for i in range(Q):
	a, b, c = getlist()
	ans = dist[a] + dist[b] + dist[c] - dist[LCA(a, b, N)] - dist[LCA(b, c, N)] - dist[LCA(c, a, N)]
	print(ans)
0