Submission #7492214


Source Code Expand

def resolve():
    import sys
    sys.setrecursionlimit(2147483647)
    INF=float("inf")
    MOD=10**9+7
    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())
    edges=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(lambda x:int(x)-1,input().split())
        edges[u].append(v)
        edges[v].append(u)
    lca=LCA(edges)
    for _ in range(int(input())):
        u,v=map(lambda x:int(x)-1,input().split())
        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 2486 Byte
Status AC
Exec Time 993 ms
Memory 152112 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 164 ms 38256 KB
subtask0_sample02.txt AC 167 ms 38384 KB
subtask0_sample03.txt AC 168 ms 38256 KB
subtask1_01.txt AC 572 ms 142896 KB
subtask1_02.txt AC 582 ms 142768 KB
subtask1_03.txt AC 164 ms 38256 KB
subtask1_04.txt AC 166 ms 38256 KB
subtask1_05.txt AC 191 ms 40816 KB
subtask1_06.txt AC 180 ms 39792 KB
subtask1_07.txt AC 436 ms 71456 KB
subtask1_08.txt AC 490 ms 77088 KB
subtask1_09.txt AC 500 ms 80416 KB
subtask1_10.txt AC 498 ms 81568 KB
subtask1_11.txt AC 538 ms 86176 KB
subtask1_12.txt AC 511 ms 85408 KB
subtask2_01.txt AC 792 ms 151728 KB
subtask2_02.txt AC 824 ms 152112 KB
subtask2_03.txt AC 490 ms 61528 KB
subtask2_04.txt AC 503 ms 61656 KB
subtask2_05.txt AC 563 ms 64856 KB
subtask2_06.txt AC 538 ms 63196 KB
subtask2_07.txt AC 946 ms 95392 KB
subtask2_08.txt AC 927 ms 95136 KB
subtask2_09.txt AC 966 ms 97568 KB
subtask2_10.txt AC 954 ms 98464 KB
subtask2_11.txt AC 993 ms 101280 KB
subtask2_12.txt AC 971 ms 101024 KB