Submission #4653159


Source Code Expand

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

LCA = list(range(N+1))

def getV(lca,inte):#inteが経由する頂点を全て返す。ただしLCAは1を基準とする。
#全ての頂点が辺でつながれない、または閉路が存在する場合兵庫県警に逮捕される
    ans = []
    while True:
        if lca[inte] == 1:
            return [1,inte]+ans
            break
        elif inte == 1:
            return [1]+ans
        else:
            ans = [inte] + ans
            inte =lca[inte]

def getD(lca,int1,int2):#int1 < int2 である方が望ましい
        
    L1 = getV(lca,int1)
    L2 = getV(lca,int2)
    length1 = -1
    length2 = 0
    for l in L1[::-1]:
        length1 += 1
        if L2.__contains__(l):
            length2 = len(L2[L2.index(l):])-1
            break
    return length1+length2
        
            
    
    
for x,y in XY:
    LCA[max(x,y)] = min(x,y) 

for a,b in AB:
    print(getD(LCA,min(a,b),max(a,b))+1)

Submission Info

Submission Time
Task D - 閉路
User BARISU
Language Python (3.4.3)
Score 0
Code Size 1114 Byte
Status TLE
Exec Time 2107 ms
Memory 56304 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
TLE × 12
AC × 3
TLE × 24
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 17 ms 3064 KB
subtask0_sample02.txt AC 17 ms 3064 KB
subtask0_sample03.txt AC 17 ms 3064 KB
subtask1_01.txt TLE 2105 ms 31292 KB
subtask1_02.txt TLE 2105 ms 31292 KB
subtask1_03.txt TLE 2104 ms 3784 KB
subtask1_04.txt TLE 2104 ms 3792 KB
subtask1_05.txt TLE 2103 ms 3976 KB
subtask1_06.txt TLE 2103 ms 3968 KB
subtask1_07.txt TLE 2106 ms 31976 KB
subtask1_08.txt TLE 2106 ms 31984 KB
subtask1_09.txt TLE 2106 ms 31984 KB
subtask1_10.txt TLE 2106 ms 31980 KB
subtask1_11.txt TLE 2106 ms 31984 KB
subtask1_12.txt TLE 2105 ms 33892 KB
subtask2_01.txt TLE 2107 ms 52468 KB
subtask2_02.txt TLE 2107 ms 54880 KB
subtask2_03.txt TLE 2105 ms 21708 KB
subtask2_04.txt TLE 2105 ms 21716 KB
subtask2_05.txt TLE 2105 ms 26684 KB
subtask2_06.txt TLE 2105 ms 26696 KB
subtask2_07.txt TLE 2107 ms 56300 KB
subtask2_08.txt TLE 2107 ms 56296 KB
subtask2_09.txt TLE 2107 ms 56292 KB
subtask2_10.txt TLE 2107 ms 56304 KB
subtask2_11.txt TLE 2107 ms 56292 KB
subtask2_12.txt TLE 2107 ms 56296 KB