Root the tree with a traversal
Treat the undirected input edges as an adjacency list and root the tree at node 1. Starting with 1 in a breadth-first search queue, each newly reached neighbor is a child of the current node. Record that relationship when the neighbor is enqueued, not when it is later removed from the queue. This marks the node as discovered immediately, so no other edge can assign it a second parent. The root is marked before traversal and has no parent to print.
A tree has exactly one path from the root to any node, so the first edge that reaches a node is its unique parent edge. After the traversal, print parent[2] through parent[N] in node order. The queue is an integer array, so the traversal uses no recursion and remains safe for a path-shaped tree with maximum depth.
There are N - 1 edges. Building the undirected adjacency lists and visiting each vertex and edge takes O(N) time. The adjacency lists, parent array, and queue take O(N) extra space.
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int n = input.nextInt();
@SuppressWarnings("unchecked")
ArrayList<Integer>[] graph = new ArrayList[n + 1];
for (int node = 1; node <= n; node++) {
graph[node] = new ArrayList<>();
}
for (int edge = 0; edge < n - 1; edge++) {
int a = input.nextInt();
int b = input.nextInt();
graph[a].add(b);
graph[b].add(a);
}
int[] parent = new int[n + 1];
int[] queue = new int[n];
int head = 0;
int tail = 0;
parent[1] = 1;
queue[tail++] = 1;
while (head < tail) {
int current = queue[head++];
for (int neighbor : graph[current]) {
if (parent[neighbor] != 0) continue;
parent[neighbor] = current;
queue[tail++] = neighbor;
}
}
StringBuilder output = new StringBuilder();
for (int node = 2; node <= n; node++) {
output.append(parent[node]).append('\n');
}
System.out.print(output);
}
private static final class FastScanner {
private final BufferedInputStream input = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int length;
private int position;
private int read() throws IOException {
if (position == length) {
length = input.read(buffer);
position = 0;
if (length == -1) return -1;
}
return buffer[position++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
}