Tests for problem D (Codeforces 1278E)
Tags: Others, divide and conquer

We had a really tough time generating tests for problem D. In order to prepare strong tests, we had to solve the following problem.Given an undirected labeled tree consisting of $$$n$$$ vertices, find a set of segments such that:  both endpoints of each segment are integers from $$$1$$$ to $$$2n$$$, and each integer from $$$1$$$ to $$$2n$$$ should appear as an endpoint of exactly one segment;  all segments are non-degenerate;  for each pair $$$(i, j)$$$ such that $$$i \ne j$$$, $$$i \in [1, n]$$$ and $$$j \in [1, n]$$$, the vertices $$$i$$$ and $$$j$$$ are connected with an edge if and only if the segments $$$i$$$ and $$$j$$$ intersect, but neither segment $$$i$$$ is fully contained in segment $$$j$$$, nor segment $$$j$$$ is fully contained in segment $$$i$$$. Can you solve this problem too?

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of vertices in the tree.Then $$$n - 1$$$ lines follow, each containing two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) denoting the endpoints of the $$$i$$$-th edge.It is guaranteed that the given graph is a tree.

Output: Print $$$n$$$ pairs of integers, the $$$i$$$-th pair should contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i < r_i \le 2n$$$) — the endpoints of the $$$i$$$-th segment. All $$$2n$$$ integers you print should be unique.It is guaranteed that the answer always exists.


Sample Inputs:
6
1 2
1 3
3 4
3 5
2 6

1

Sample Outputs:
9 12
7 10
3 11
1 5
2 4
6 8

1 2

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def dfs():
    st = [1]
    visit = [0] * (n + 1)
    visit[1] = 1
    now = 1
    (l, r) = ([0] * (n + 1), [0] * (n + 1))
    l[1] = 1
    while st:
        f = 0
        i = st[-1]
        for j in G[i]:
            if visit[j]:
                continue
            f = 1
            now += 1
            l[j] = now
            visit[j] = 1
            st.append(j)
        if f:
            now += 1
            r[i] = now
        else:
            if not r[i]:
                now += 1
                r[i] = now
            st.pop()
    return (l[1:], r[1:])
n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    (x, y) = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
(l, r) = dfs()
ans = []
for (i, j) in zip(l, r):
    ans.append(' '.join(map(str, (i, j))))
sys.stdout.write('\n'.join(ans))

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    adj = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        (a, b) = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)
    st = [1]
    seen = [0] * (N + 1)
    seen[1] = 1
    LL = [0] * (2 * N + 3)
    LL[-1] = 1
    LL[1] = 0
    LL_rev = [0] * (2 * N + 3)
    LL_rev[1] = -1
    LL_rev[-1] = 0
    st_append = st.append
    while st:
        v = st.pop()
        for u in adj[v]:
            if not seen[u]:
                seen[u] = 1
                st_append(u)
                v_next = LL[v]
                v_prev = LL_rev[v]
                LL[v] = u
                LL[u] = v_next
                LL_rev[v_next] = u
                LL_rev[u] = v
                u_ = -u
                LL_rev[v] = u_
                LL[v_prev] = u_
                LL[u_] = v
    s = -1
    ans1 = [0] * (N + 1)
    ans2 = [0] * (N + 1)
    for i in range(1, 2 * N + 1):
        if s < 0:
            ans1[-s] = i
        else:
            ans2[s] = i
        s = LL[s]
    ans = '\n'.join([' '.join(map(str, [ans1[i], ans2[i]])) for i in range(1, N + 1)])
    sys.stdout.write(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
_str = str
str = lambda x=b'': x if type(x) is bytes else _str(x).encode()
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def process(n, G):
    g = [[] for i in range(n + 1)]
    answer = [[None, None] for i in range(n + 1)]
    children = [[] for i in range(n + 1)]
    seen = [0 for i in range(n + 1)]
    for (x, y) in G:
        g[x].append(y)
        g[y].append(x)
    start = [[1, 0]]
    I = 1
    while True:
        (x, t) = start[-1]
        if t == 0:
            seen[x] = 1
            if answer[x][0] is None:
                answer[x][0] = I
                I += 1
            m = len(g[x])
            for i in range(m - 1, -1, -1):
                y = g[x][i]
                if answer[y][0] is None:
                    answer[y][0] = I
                    children[x].append(y)
                    I += 1
            answer[x][1] = I
            I += 1
        if t == len(children[x]):
            start.pop()
            if len(start) > 0:
                start[-1][1] += 1
            else:
                break
        else:
            x2 = children[x][len(children[x]) - 1 - t]
            start.append([x2, 0])
    for i in range(1, n + 1):
        (l, r) = answer[i]
        sys.stdout.write(f'{l} {r}\n')
    return
n = int(input())
G = []
for i in range(n - 1):
    (x, y) = [int(x) for x in input().split()]
    G.append([x, y])
process(n, G)