Submission #54242089

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque
class LCA:
    def __init__(self, G, root=0):
        V = len(G)
        K = 1
        while 1<<K < V:
            K += 1
        self.parent = [[-1]*V for _ in range(K)]
        self.dist = [-1]*V
        self.bfs(G, root)
        for i in range(K-1):
            for j in range(V):
                if self.parent[i][j] != -1:
                    self.parent[i+1][j] = self.parent[i][self.parent[i][j]]
        
    def bfs(self, G, root):
        self.dist[root] = 0
        que = deque()
        que.append(root)
        while que:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque

class LCA:
    def __init__(self, G, root=0):
        V = len(G)
        K = 1
        while 1<<K < V:
            K += 1
        self.parent = [[-1]*V for _ in range(K)]
        self.dist = [-1]*V
        self.bfs(G, root)
        for i in range(K-1):
            for j in range(V):
                if self.parent[i][j] != -1:
                    self.parent[i+1][j] = self.parent[i][self.parent[i][j]]
        
    def bfs(self, G, root):
        self.dist[root] = 0
        que = deque()
        que.append(root)
        while que:
            n = que.popleft()
            for v in G[n]:
                if self.dist[v] == -1:
                    self.dist[v] = self.dist[n]+1
                    self.parent[0][v] = n
                    que.append(v)
    
    def query(self, a, b):
        if self.dist[a] < self.dist[b]:
            a, b = b, a
        K = len(self.parent)
        for i in range(K):
            if (self.dist[a]-self.dist[b]) & 1<<i:
                a = self.parent[i][a]
        if a == b:
            return a
        for i in reversed(range(K)):
            if self.parent[i][a] != self.parent[i][b]:
                a = self.parent[i][a]
                b = self.parent[i][b]
        return self.parent[0][a]

N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
Q = int(input())
ab = [list(map(int, input().split())) for _ in range(Q)]

lca = LCA(edge)
for a, b in ab:
    a-=1; b-=1
    c = lca.query(a, b)
    ans = lca.dist[a] + lca.dist[b] - 2 * lca.dist[c] + 1
    print(ans)

Submission Info

Judge Result