Submission #5897819


Source Code Expand

class Lca:
    def __init__(self, E, root):
        import sys
        sys.setrecursionlimit(500000)
        self.root = root
        self.E = E  # V<V>
        self.n = len(E)  # 頂点数
        self.logn = 1
        while self.n >= (1<<self.logn):
            self.logn += 1

        self.parent = [[-1]*self.n for _ in range(self.logn)]

        self.depth = [0] * self.n
        self.dfs(root, -1, 0)
        for k in range(self.logn-1):
            for v in range(self.n):
                p_ = self.parent[k][v]
                if p_ >= 0:
                    self.parent[k+1][v] = self.parent[k][p_]

    def dfs(self, v, p, dep):
        self.parent[0][v] = p
        self.depth[v] = dep
        for e in self.E[v]:
            if e != p:
                self.dfs(e, v, dep+1)

    def get(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        dep_diff = self.depth[v]-self.depth[u]
        for k in range(self.logn):
            if dep_diff >> k & 1:
                v = self.parent[k][v]
        if u==v:
            return u
        for k in range(self.logn-1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]
N = int(input())
xy = {}
for i in range(N):
    xy[i] = []

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

lca = Lca(xy,0)

Q = int(input())
for i in range(Q):
    a,b = map(int,input().split())
    q = lca.get(a-1,b-1)
    print(lca.depth[a-1] + lca.depth[b-1] - 2*lca.depth[q] + 1)

Submission Info

Submission Time
Task D - 閉路
User alexara1123
Language PyPy3 (2.4.0)
Score 30
Code Size 1680 Byte
Status TLE
Exec Time 2024 ms
Memory 163940 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 0 / 70
Status
AC × 3
AC × 12
AC × 26
TLE × 1
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 163 ms 38384 KB
subtask0_sample02.txt AC 161 ms 38256 KB
subtask0_sample03.txt AC 163 ms 38256 KB
subtask1_01.txt AC 884 ms 157284 KB
subtask1_02.txt AC 867 ms 155108 KB
subtask1_03.txt AC 163 ms 38256 KB
subtask1_04.txt AC 167 ms 38256 KB
subtask1_05.txt AC 212 ms 41072 KB
subtask1_06.txt AC 204 ms 40176 KB
subtask1_07.txt AC 727 ms 79972 KB
subtask1_08.txt AC 770 ms 85092 KB
subtask1_09.txt AC 769 ms 88804 KB
subtask1_10.txt AC 796 ms 90340 KB
subtask1_11.txt AC 803 ms 94436 KB
subtask1_12.txt AC 793 ms 94308 KB
subtask2_01.txt AC 1768 ms 163940 KB
subtask2_02.txt AC 1795 ms 163812 KB
subtask2_03.txt AC 1187 ms 55640 KB
subtask2_04.txt AC 1209 ms 55384 KB
subtask2_05.txt AC 1252 ms 59352 KB
subtask2_06.txt AC 1220 ms 60124 KB
subtask2_07.txt AC 1981 ms 99428 KB
subtask2_08.txt AC 1942 ms 96484 KB
subtask2_09.txt AC 1968 ms 99300 KB
subtask2_10.txt AC 1979 ms 102884 KB
subtask2_11.txt AC 2000 ms 105480 KB
subtask2_12.txt TLE 2024 ms 105188 KB