Submission #9925357


Source Code Expand

Copy
import sys


class LcaDoubling:
    """
    links[v] = { (u, w), (u, w), ... }  (u:隣接頂点, w:辺の重み)
    というグラフ情報から、ダブリングによるLCAを構築。
    任意の2頂点のLCAおよび距離を取得できるようにする
    """

    def __init__(self, n, links, root=0):
        self.depths = [-1] * n
        self.distances = [-1] * n
        prev_ancestors = self._init_dfs(n, links, root)
        self.ancestors = [prev_ancestors]
        max_depth = max(self.depths)
        d = 1
        while d < max_depth:
            next_ancestors = [prev_ancestors[p] for p in prev_ancestors]
            self.ancestors.append(next_ancestors)
            d <<= 1
            prev_ancestors = next_ancestors

    def _init_dfs(self, n, links, root):
        q = [(root, -1, 0, 0)]
        direct_ancestors = [-1] * (n + 1)  # 頂点数より1個長くし、存在しないことを-1で表す。末尾(-1)要素は常に-1
        while q:
            v, p, dep, dist = q.pop()
            direct_ancestors[v] = p
            self.depths[v] = dep
            self.distances[v] = dist
            q.extend((u, v, dep + 1, dist + w) for u, w in links[v] if u != p)
        return direct_ancestors

    def get_lca(self, u, v):
        du, dv = self.depths[u], self.depths[v]
        if du > dv:
            u, v = v, u
            du, dv = dv, du
        tu = u
        tv = self.upstream(v, dv - du)
        if u == tv:
            return u
        for k in range(du.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

    def get_distance(self, u, v):
        lca = self.get_lca(u, v)
        return self.distances[u] + self.distances[v] - 2 * self.distances[lca]

    def upstream(self, v, k):
        i = 0
        while k:
            if k & 1:
                v = self.ancestors[i][v]
            k >>= 1
            i += 1
        return v


n = int(input())
links = [set() for _ in range(n)]
lines = sys.stdin.readlines()
for line in lines[:n - 1]:
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    links[x].add((y, 1))
    links[y].add((x, 1))

lcad = LcaDoubling(n, links)

for line in lines[n:]:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    d = lcad.get_distance(a, b)
    print(d + 1)

Submission Info

Submission Time
Task D - 閉路
User ikatakos
Language Python (3.4.3)
Score 100
Code Size 2569 Byte
Status AC
Exec Time 1438 ms
Memory 83132 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 3
AC × 12
AC × 27
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 17 ms 3192 KB
subtask0_sample02.txt AC 18 ms 3192 KB
subtask0_sample03.txt AC 18 ms 3192 KB
subtask1_01.txt AC 506 ms 74940 KB
subtask1_02.txt AC 498 ms 74940 KB
subtask1_03.txt AC 18 ms 3192 KB
subtask1_04.txt AC 18 ms 3192 KB
subtask1_05.txt AC 22 ms 3572 KB
subtask1_06.txt AC 22 ms 3572 KB
subtask1_07.txt AC 519 ms 60864 KB
subtask1_08.txt AC 540 ms 59836 KB
subtask1_09.txt AC 565 ms 60992 KB
subtask1_10.txt AC 594 ms 65084 KB
subtask1_11.txt AC 606 ms 68032 KB
subtask1_12.txt AC 607 ms 65212 KB
subtask2_01.txt AC 1124 ms 83132 KB
subtask2_02.txt AC 1139 ms 83008 KB
subtask2_03.txt AC 466 ms 11072 KB
subtask2_04.txt AC 548 ms 11012 KB
subtask2_05.txt AC 691 ms 12220 KB
subtask2_06.txt AC 666 ms 12268 KB
subtask2_07.txt AC 1159 ms 69692 KB
subtask2_08.txt AC 1210 ms 68544 KB
subtask2_09.txt AC 1335 ms 69696 KB
subtask2_10.txt AC 1438 ms 73148 KB
subtask2_11.txt AC 1436 ms 76040 KB
subtask2_12.txt AC 1433 ms 73148 KB