結果

問題 No.386 貪欲な領主
ユーザー kept1994kept1994
提出日時 2021-09-16 02:54:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 618 ms / 2,000 ms
コード長 3,884 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 111,124 KB
最終ジャッジ日時 2024-06-29 03:10:37
合計ジャッジ時間 6,004 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#!/usr/bin/env python3
import sys
class LcaDoubling:
#
def __init__(self, N, root=0):
self.N = N
self.root = root
self.G = [[] for _ in range(N)]
self.depths = [-1] * N
self.distances = [-1] * N
self.ancestors = []
return
def addEdge(self, a: int, b: int, cost: int):
self.G[a].append((cost, b))
self.G[b].append((cost, a))
return
def build(self):
prevAncestors = self._dfs()
self.ancestors.append(prevAncestors)
d = 1
max_depth = max(self.depths)
while d < max_depth:
nextAncestors = [prevAncestors[p] for p in prevAncestors]
self.ancestors.append(nextAncestors)
d <<= 1
prevAncestors = nextAncestors
return
def _dfs(self):
q = [(self.root, -1, 0, 0)]
directAncestors = [-1] * (self.N + 1) # 1-1(-1)-1
while q:
now, parent, dep, dist = q.pop()
directAncestors[now] = parent
self.depths[now] = dep
self.distances[now] = dist
for cost, next in self.G[now]:
if next != parent:
q.append((next, now, dep + 1, dist + cost))
return directAncestors
def getLca(self, nodeA: int, nodeB: int):
depthA, depthB = self.depths[nodeA], self.depths[nodeB]
if depthA > depthB:
nodeA, nodeB = nodeB, nodeA
depthA, depthB = depthB, depthA
# 2
tu = nodeA
tv = self.upstream(nodeB, depthB - depthA)
# 2
if nodeA == tv:
return nodeA
for k in range(depthA.bit_length() - 1, -1, -1):
mu = self.ancestors[k][tu]
mv = self.ancestors[k][tv]
if mu != mv:
tu = mu
tv = mv
lca = self.ancestors[0][tu]
assert lca == self.ancestors[0][tv]
return lca
# 2
def getDistance(self, nodeA, nodeB):
lca = self.getLca(nodeA, nodeB)
return self.distances[nodeA] + self.distances[nodeB] - 2 * self.distances[lca]
# targetNode2
def isOnPath(self, nodeA: int, nodeB: int, evalNode: int):
return self.getDistance(nodeA, nodeB) == self.getDistance(nodeA, evalNode) + self.getDistance(evalNode, nodeB)
# vk
def upstream(self, v, k):
i = 0
while k:
if k & 1:
v = self.ancestors[i][v]
k >>= 1
i += 1
return v
def main():
N = int(input())
ld = LcaDoubling(N)
for _ in range(N - 1):
a, b = map(int, input().split())
ld.addEdge(a, b, 1)
ld.build()
U = [int(input()) for _ in range(N)]
from collections import deque
def bfs(edges: "List[to]", start_node: int) -> list:
q = deque()
dist = [0] * len(edges)
q.append(start_node)
dist[start_node] = U[0]
while q:
now = q.popleft()
for _, next in edges[now]:
if dist[next] != 0:
continue
q.append(next)
dist[next] = dist[now] + U[next]
return dist
d = bfs(ld.G, 0)
M = int(input())
ans = 0
for _ in range(M):
u, v, e = map(int, input().split())
lca = ld.getLca(u, v)
ans += (d[u] + d[v] - 2 * d[lca] + U[lca]) * e
print(ans)
return
if __name__ == '__main__':
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0