Submission #7491516


Source Code Expand

def resolve():
    import math
    import sys
    class DoublingLCA:
        """
        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)
            self.logn = (self.n-1).bit_length()
            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):
            stack=[(par,cur,dep)]
            while(stack):
                par,cur,dep=stack.pop()
                self.depths[cur]=dep
                self.parents[0][cur]=par
                for v in self.edges[cur]:
                    if self.depths[v]==-1:
                        stack.append((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] < 0: # 親が存在しないとき。-1を通すとlistの末尾を取得してしまう
                        continue
                    self.parents[i][v]=self.parents[i-1][self.parents[i-1][v]]

        def get(self, u, v):
            # 深さを合わせる
            dd=self.depths[v]-self.depths[u]
            if dd<0:
                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]

    # sys.stdin.readline
    N = int(sys.stdin.readline())
    XY = [list(map(int, sys.stdin.readline().split())) for _ in range(N-1)]
    Q = int(sys.stdin.readline())
    AB = [list(map(int, sys.stdin.readline().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 = DoublingLCA(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 100
Code Size 2523 Byte
Status AC
Exec Time 856 ms
Memory 117084 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 162 ms 38256 KB
subtask0_sample02.txt AC 163 ms 38256 KB
subtask0_sample03.txt AC 169 ms 38256 KB
subtask1_01.txt AC 341 ms 82012 KB
subtask1_02.txt AC 341 ms 82012 KB
subtask1_03.txt AC 166 ms 38256 KB
subtask1_04.txt AC 163 ms 38256 KB
subtask1_05.txt AC 182 ms 40048 KB
subtask1_06.txt AC 191 ms 40316 KB
subtask1_07.txt AC 398 ms 83164 KB
subtask1_08.txt AC 411 ms 83292 KB
subtask1_09.txt AC 396 ms 82780 KB
subtask1_10.txt AC 405 ms 83292 KB
subtask1_11.txt AC 400 ms 82780 KB
subtask1_12.txt AC 403 ms 83292 KB
subtask2_01.txt AC 553 ms 103388 KB
subtask2_02.txt AC 553 ms 103644 KB
subtask2_03.txt AC 469 ms 73820 KB
subtask2_04.txt AC 473 ms 74332 KB
subtask2_05.txt AC 537 ms 74788 KB
subtask2_06.txt AC 519 ms 73564 KB
subtask2_07.txt AC 804 ms 116828 KB
subtask2_08.txt AC 823 ms 117084 KB
subtask2_09.txt AC 829 ms 116572 KB
subtask2_10.txt AC 822 ms 115164 KB
subtask2_11.txt AC 856 ms 115420 KB
subtask2_12.txt AC 853 ms 115804 KB