Submission #2745282


Source Code Expand

Copy
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, sys.stdin.readline().split())
    x, y = x-1, y-1
    G[x].append(y)
    G[y].append(x)

parent = [[] for i in range(N)]  # 親を2^k回辿って到達する頂点
depth = [None] * N
stack = []


def walk(i):
    rec_size = len(stack)
    depth[i] = rec_size

    # 親を2^k回辿る
    k = 0
    while 2**k <= rec_size:
        parent[i].append(stack[rec_size-2**k])
        k += 1

    stack.append(i)

    for ni in G[i]:
        if depth[ni] is not None:
            continue
        walk(ni)
    del stack[-1]


walk(0)

Q = int(input())
for i in range(Q):
    a, b = map(int, sys.stdin.readline().split())
    a, b = a-1, b-1
    if depth[a] > depth[b]:  # 深いほうが後ろ
        a, b = b, a

    depth_add = depth[a] + depth[b]
    depth_diff = depth[b] - depth[a]

    while depth_diff > 0:

        k = 1
        while 2**k < depth_diff:
            k += 1
        k -= 1

        b = parent[b][k]
        depth_diff -= 2**k

    while a != b:
        k = 1
        le = len(parent[a])

        while le > k and parent[a][k] != parent[b][k]:
            k += 1
        k -= 1
        a = parent[a][k]
        b = parent[b][k]

    print(depth_add - 2*depth[a] + 1)

Submission Info

Submission Time
Task D - 閉路
User kenseiQ
Language PyPy3 (2.4.0)
Score 100
Code Size 1379 Byte
Status
Exec Time 1616 ms
Memory 164016 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
Subtask1 30 / 30 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 70 / 70 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 167 ms 38768 KB
subtask0_sample02.txt 162 ms 38256 KB
subtask0_sample03.txt 161 ms 38256 KB
subtask1_01.txt 1244 ms 163504 KB
subtask1_02.txt 1196 ms 158384 KB
subtask1_03.txt 161 ms 38256 KB
subtask1_04.txt 169 ms 38256 KB
subtask1_05.txt 187 ms 41180 KB
subtask1_06.txt 187 ms 41324 KB
subtask1_07.txt 433 ms 71840 KB
subtask1_08.txt 439 ms 70192 KB
subtask1_09.txt 497 ms 72752 KB
subtask1_10.txt 494 ms 76720 KB
subtask1_11.txt 623 ms 77360 KB
subtask1_12.txt 463 ms 73648 KB
subtask2_01.txt 1616 ms 164016 KB
subtask2_02.txt 1592 ms 162864 KB
subtask2_03.txt 410 ms 57436 KB
subtask2_04.txt 459 ms 58968 KB
subtask2_05.txt 522 ms 55900 KB
subtask2_06.txt 600 ms 63064 KB
subtask2_07.txt 798 ms 85664 KB
subtask2_08.txt 765 ms 82992 KB
subtask2_09.txt 895 ms 89776 KB
subtask2_10.txt 931 ms 90800 KB
subtask2_11.txt 995 ms 99504 KB
subtask2_12.txt 878 ms 87728 KB