Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class SegmentTree:
- def __init__(self, array):
- self.n = len(array)
- self.size = 1
- while self.size <= n:self.size*=2
- self.func = lambda x, y: x if x[0] < y[0] else y
- self.default = (10**9, -1)
- self.data = [self.default] * (2 * self.size)
- self.process(array)
- def process(self, array):
- self.data[self.size : self.size+self.n] = array
- for i in range(self.size-1, -1, -1):
- self.data[i] = self.func(self.data[2*i], self.data[2*i+1])
- def query(self, alpha, omega):
- """Returns the result of function over the range (inclusive)!"""
- if alpha == omega:
- return self.data[alpha + self.size]
- res = self.default
- alpha += self.size
- omega += self.size + 1
- while alpha < omega:
- if alpha & 1:
- res = self.func(res, self.data[alpha])
- alpha += 1
- if omega & 1:
- omega -= 1
- res = self.func(res, self.data[omega])
- alpha >>= 1
- omega >>= 1
- return res
- def update(self, index, value):
- """Updates the element at index to given value!"""
- index += self.size
- self.data[index] = value
- index >>= 1
- while index:
- self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
- index >>= 1
- class LCA:
- def __init__(self, graph, root):
- self.graph= graph
- self.n = len(graph)
- self.euler = []
- self.first = [-1]*self.n
- self.st = None
- self.dfs(root)
- self.process()
- def dfs(self, root):
- visited, parents, heights = [False]*self.n, [-1]*self.n, [1]*self.n
- stack = [root]
- while stack:
- v = stack[-1]
- if not visited[v]:
- visited[v] = True
- self.euler += [v]
- if self.first[v] == -1:
- self.first[v] = len(self.euler) - 1
- for u in graph[v]:
- if not visited[u]:
- stack.append(u)
- parents[u], heights[u] = v, heights[v] + 1
- else:
- self.euler += [parents[stack.pop()]]
- self.euler = [(heights[k], k) for k in self.euler]
- def process(self):
- self.st = SegmentTree(self.euler)
- def query(self, x, y):
- """Returns the lowest common ancestor of nodes x and y!"""
- p, q = min(self.first[x], self.first[y]), max(self.first[x], self.first[y])
- return self.st.query(p, q)[1]
- import sys
- input = sys.stdin.readline
- for _ in range(1, int(input()) + 1):
- n = int(input())
- graph = [[] for __ in range(n+1)]
- for i in range(1, n+1):
- for j in list(map(int, input().split()))[1:]:
- graph[i] += [j]
- graph[j] += [i]
- lca = LCA(graph, 1)
- print("Case %d:" % _)
- for __ in range(int(input())):
- x, y = map(int, input().split())
- print(lca.query(x, y))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement