def eulerTour(root):
euler = []
depth = []
first = [-1] * n # first occurrence
def dfs(node, d, parent):
first[node] = len(euler)
euler.append(node)
depth.append(d)
for child in adj[node]:
if child != parent:
dfs(child, d + 1, node)
euler.append(node)
depth.append(d)
dfs(root, 0, -1)
return euler, depth, first
Tour length is (we enter each node once and return after each child).
Build Sparse Table on the depth array. Query returns the index of minimum depth; use euler array to get the actual node.