An Euler tour flattens a tree so that every subtree becomes a contiguous range. Do a DFS from the root with a timer that starts at 0:
- when you first enter
v, settin[v] = timerand add one totimer; - after all of
v's children are finished, settout[v] = timer.
Then the subtree of v is exactly the nodes u with tin[v] <= tin[u] < tout[v], and tout[v] - tin[v] is the size of that subtree.
The tree has nodes 0 .. n-1 and edges is a list of n - 1 undirected pairs (a, b). Implement euler_tour(n, edges, root) -> tuple[list[int], list[int]] returning (tin, tout). Any child order is accepted.
# 0
# / \
# 1 2
# |
# 3
euler_tour(4, [(0, 1), (0, 2), (2, 3)], 0)
# ([0, 1, 2, 3], [4, 2, 4, 4]) visiting child 1 before child 2
# ([0, 3, 1, 2], [4, 4, 3, 3]) visiting child 2 before child 1 is also fine
Constraints: 1 <= n <= 10^5. The tests include a path of 100,000 nodes, so a recursive DFS will hit Python's recursion limit: use an explicit stack.
Show hint
push (node, parent, exiting) entries on a stack. On the entering visit, record tin, push the exit marker for the node, then push its children; on the exit visit, record tout = timer.