Submission #7492172


Source Code Expand

def resolve():
    import sys
    input=sys.stdin.readline
    class LCA:
        """
        construct: O(NlogN)
        query: O(logN)
        """

        def __init__(self,edges,root=0):
            """
            :param list of (list of int) edges:
            :param int root=0:
            """
            self.edges = edges
            self.n = len(edges) # n=|V|
            self.logn = (self.n-1).bit_length() # logn=ceil(log2(n))
            self.depths = [-1] * self.n
            self.parents = [[-1] * self.n for _ in range(self.logn)]
            # construct
            self.__dfs(-1,root,0)
            self.__doubling()

        def __dfs(self,par,cur,dep):
            self.depths[cur]=dep
            self.parents[0][cur]=par
            for v in self.edges[cur]:
                if self.depths[v]==-1: # 深さ-1=訪れていない(rootから連結な部分しか探索しない)
                    self.__dfs(cur,v,dep+1)

        def __doubling(self):
            for i in range(1,self.logn):
                for v in range(self.n):
                    if self.parents[i-1][v]==-1: # 親が存在しないとき。-1を通すとlistの末尾を取得してしまう
                        continue
                    self.parents[i][v]=self.parents[i-1][self.parents[i-1][v]]

        def get(self,u,v): # u,vのLCAを返す
            dd=self.depths[v]-self.depths[u]
            if dd<0: # vの方が深いようにする
                u,v=v,u
                dd*=-1
            for i in range(self.logn):
                if dd&(1<<i):
                    v = self.parents[i][v]

            if v==u: return v # 高さ揃えた時点で一致してたら終わり

            # そうでなければ上から二分探索
            for i in reversed(range(self.logn)):
                pu,pv=self.parents[i][u],self.parents[i][v]
                if pu!=pv:
                    u,v=pu,pv
            return self.parents[0][u]

    # input
    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N-1)]
    Q = int(input())
    AB = [list(map(int, input().split())) for _ in range(Q)]

    edges = [[] for _ in range(N)]
    for x, y in XY:
        edges[x-1].append(y-1)
        edges[y-1].append(x-1)
    lca = LCA(edges)

    for u,v in AB:
        u=u-1
        v=v-1
        print(lca.depths[u]+lca.depths[v]-2*lca.depths[lca.get(u,v)]+1)

resolve()

Submission Info

Submission Time
Task D - 閉路
User moni0627
Language PyPy3 (2.4.0)
Score 0
Code Size 2480 Byte
Status RE
Exec Time 1094 ms
Memory 125020 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
AC × 10
RE × 2
AC × 23
RE × 4
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 174 ms 38256 KB
subtask0_sample02.txt AC 172 ms 38256 KB
subtask0_sample03.txt AC 171 ms 38256 KB
subtask1_01.txt RE 439 ms 84316 KB
subtask1_02.txt RE 435 ms 84316 KB
subtask1_03.txt AC 178 ms 38256 KB
subtask1_04.txt AC 171 ms 38256 KB
subtask1_05.txt AC 196 ms 41200 KB
subtask1_06.txt AC 189 ms 40304 KB
subtask1_07.txt AC 462 ms 86236 KB
subtask1_08.txt AC 538 ms 92508 KB
subtask1_09.txt AC 537 ms 95196 KB
subtask1_10.txt AC 528 ms 96476 KB
subtask1_11.txt AC 572 ms 100828 KB
subtask1_12.txt AC 530 ms 100188 KB
subtask2_01.txt RE 533 ms 99548 KB
subtask2_02.txt RE 537 ms 99548 KB
subtask2_03.txt AC 492 ms 74076 KB
subtask2_04.txt AC 531 ms 74204 KB
subtask2_05.txt AC 548 ms 76764 KB
subtask2_06.txt AC 537 ms 75484 KB
subtask2_07.txt AC 1094 ms 121692 KB
subtask2_08.txt AC 1030 ms 121180 KB
subtask2_09.txt AC 1080 ms 121436 KB
subtask2_10.txt AC 1022 ms 122076 KB
subtask2_11.txt AC 1063 ms 123484 KB
subtask2_12.txt AC 1015 ms 125020 KB