結果

問題 No.3309 Aging Railway
コンテスト
ユーザー norioc
提出日時 2025-11-05 10:31:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 785 ms / 3,000 ms
コード長 2,917 bytes
コンパイル時間 2,785 ms
コンパイル使用メモリ 81,956 KB
実行使用メモリ 80,804 KB
最終ジャッジ日時 2025-11-05 10:31:49
合計ジャッジ時間 14,496 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
from itertools import accumulate


class LcaEdgeMinWeight:
    def __init__(self, n: int, adj: dict, root=0):
        """
        n: 頂点数
        adj: { 頂点: [(隣接頂点, 重み), ...] }
        root: 根
        """
        sz = n.bit_length()
        parents = [[-1] * n for _ in range(sz)]
        dists = [-1] * n
        min_weights = [[INF] * n for _ in range(sz)]

        def dfs():
            s = [(root, -1, 0, 0)]
            while s:
                v, par, depth, weight = s.pop()
                parents[0][v] = par
                dists[v] = depth
                min_weights[0][v] = weight
                for to, w in adj[v]:
                    if to == par: continue
                    s.append((to, v, depth+1, w))

        dfs()
        for k in range(sz-1):
            for v in range(n):
                if parents[k][v] < 0: continue
                parents[k+1][v] = parents[k][parents[k][v]]
                min_weights[k+1][v] = min(min_weights[k][v],
                                          min_weights[k][parents[k][v]])
        self.parents = parents
        self.dists = dists
        self.min_weights = min_weights

    def find_min(self, u: int, v: int) -> int:
        """頂点間 (u, v) の辺の最小重みを求める"""
        if self.dists[u] < self.dists[v]:
            u, v = v, u

        min_w = INF
        sz = len(self.parents)
        # LCA までの距離を同じにする
        for k in range(sz):
            if (self.dists[u] - self.dists[v]) >> k & 1:
                min_w = min(min_w, self.min_weights[k][u])
                u = self.parents[k][u]

        if u == v: return min_w
        for k in range(sz-1, -1, -1):
            if self.parents[k][u] != self.parents[k][v]:
                min_w = min(min_w,
                            self.min_weights[k][u],
                            self.min_weights[k][v])
                u = self.parents[k][u]
                v = self.parents[k][v]

        return min(min_w,
                   self.min_weights[0][u],
                   self.min_weights[0][v])

    def distance(self, u: int, v: int) -> int:
        """二頂点 u, v の距離"""
        return self.dists[u] + self.dists[v] - 2 * self.dists[self.find(u, v)]

    def is_on_path(self, u: int, v: int, a: int) -> bool:
        """二頂点 u, v 上に頂点 a があるか"""
        return self.distance(u, a) + self.distance(a, v) == self.distance(u, v)


INF = 1 << 60
N, M = map(int, input().split())
adj = defaultdict(list)
for i in range(N-1):
    u, v = map(lambda x: int(x)-1, input().split())
    adj[u].append((v, i))
    adj[v].append((u, i))

lca = LcaEdgeMinWeight(N, adj)

imos = [0] * N
for _ in range(M):
    s, t = map(lambda x: int(x)-1, input().split())

    w = lca.find_min(s, t)
    imos[0] += 1
    imos[w+1] -= 1

ans = list(accumulate(imos))
print(*ans[1:], sep='\n')
0