結果

問題 No.898 tri-βutree
ユーザー 双六双六
提出日時 2019-10-05 10:46:12
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 3,587 ms / 4,000 ms
コード長 2,278 bytes
コンパイル時間 346 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 69,384 KB
最終ジャッジ日時 2024-04-15 12:38:08
合計ジャッジ時間 60,891 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,802 ms
67,384 KB
testcase_01 AC 36 ms
11,264 KB
testcase_02 AC 36 ms
11,392 KB
testcase_03 AC 36 ms
11,520 KB
testcase_04 AC 37 ms
11,392 KB
testcase_05 AC 37 ms
11,520 KB
testcase_06 AC 37 ms
11,392 KB
testcase_07 AC 3,526 ms
69,228 KB
testcase_08 AC 3,587 ms
69,140 KB
testcase_09 AC 3,546 ms
69,052 KB
testcase_10 AC 3,544 ms
69,260 KB
testcase_11 AC 3,568 ms
69,248 KB
testcase_12 AC 3,526 ms
69,356 KB
testcase_13 AC 3,543 ms
69,208 KB
testcase_14 AC 3,563 ms
69,248 KB
testcase_15 AC 3,561 ms
69,268 KB
testcase_16 AC 3,586 ms
69,384 KB
testcase_17 AC 3,517 ms
69,236 KB
testcase_18 AC 3,491 ms
69,252 KB
testcase_19 AC 3,494 ms
69,204 KB
testcase_20 AC 3,560 ms
69,336 KB
testcase_21 AC 3,571 ms
69,240 KB
権限があれば一括ダウンロードができます

ソースコード

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