1class Solution {
2    public String findSpecialNodes(int n, int[][] edges) {
3        // Build an adjacency list representation of the tree.
4        List<Integer>[] graph = new ArrayList[n];
5        Arrays.setAll(graph, k -> new ArrayList<>());
6        for (int[] edge : edges) {
7            int u = edge[0];
8            int v = edge[1];
9            graph[u].add(v);
10            graph[v].add(u);
11        }
12
13        // Holds the result of a BFS traversal:
14        // - farthest: the node farthest from the start node
15        // - distances: distance from the start node to every other node
16        record BFSResult(int farthest, int[] distances) {
17        }
18
19        // BFS from a given start node.
20        // Returns the farthest reachable node and the distance array.
21        IntFunction<BFSResult> bfs = (int start) -> {
22            int[] distances = new int[n];
23            Arrays.fill(distances, -1);
24            distances[start] = 0;
25
26            ArrayDeque<Integer> queue = new ArrayDeque<>();
27            queue.add(start);
28
29            int farthest = start;
30            while (!queue.isEmpty()) {
31                int u = queue.poll();
32                // Track the node with the maximum distance seen so far.
33                if (distances[u] > distances[farthest]) {
34                    farthest = u;
35                }
36                for (int v : graph[u]) {
37                    // Visit each unvisited neighbor exactly once.
38                    if (distances[v] == -1) {
39                        distances[v] = distances[u] + 1;
40                        queue.add(v);
41                    }
42                }
43            }
44            return new BFSResult(farthest, distances);
45        };
46
47        // Step 1: BFS from an arbitrary node (0) to find one end of the diameter.
48        int endpointA = bfs.apply(0).farthest();
49
50        // Step 2: BFS from endpointA to find the other end of the diameter.
51        BFSResult resultFromA = bfs.apply(endpointA);
52        int endpointB = resultFromA.farthest();
53        int[] distFromA = resultFromA.distances();
54
55        // Step 3: BFS from endpointB to get distances from the other diameter end.
56        int[] distFromB = bfs.apply(endpointB).distances();
57
58        // The length of the diameter.
59        int diameter = distFromA[endpointB];
60
61        // A node is "special" if it lies at the end of some diameter-length path,
62        // i.e. its distance to endpointA or endpointB equals the diameter length.
63        char[] answer = new char[n];
64        Arrays.fill(answer, '0');
65        for (int i = 0; i < n; i++) {
66            if (distFromA[i] == diameter || distFromB[i] == diameter) {
67                answer[i] = '1';
68            }
69        }
70        return new String(answer);
71    }
72}
73

1class Solution {
2public:
3    string findSpecialNodes(int n, vector<vector<int>>& edges) {
4        // Build the adjacency list for the tree.
5        vector<vector<int>> graph(n);
6        for (const auto& edge : edges) {
7            int u = edge[0], v = edge[1];
8            graph[u].push_back(v);
9            graph[v].push_back(u);
10        }
11
12        // BFS from a given source.
13        // Returns the farthest node from the source and the distance array.
14        auto bfs = [&](int source) -> pair<int, vector<int>> {
15            vector<int> distance(n, -1);
16            distance[source] = 0;
17            deque<int> queue;
18            queue.push_back(source);
19            int farthest = source;
20            while (!queue.empty()) {
21                int current = queue.front();
22                queue.pop_front();
23                // Track the node with the maximum distance seen so far.
24                if (distance[current] > distance[farthest]) {
25                    farthest = current;
26                }
27                // Visit all unvisited neighbors.
28                for (int next : graph[current]) {
29                    if (distance[next] == -1) {
30                        distance[next] = distance[current] + 1;
31                        queue.push_back(next);
32                    }
33                }
34            }
35            return {farthest, distance};
36        };
37
38        // Step 1: BFS from an arbitrary node (0) to find one endpoint
39        // of the tree's diameter.
40        auto [endpointA, distFromZero] = bfs(0);
41
42        // Step 2: BFS from endpointA to find the opposite endpoint
43        // and the distance from endpointA to every node.
44        auto [endpointB, distFromA] = bfs(endpointA);
45
46        // Step 3: BFS from endpointB to get the distance from endpointB
47        // to every node.
48        auto [unusedEndpoint, distFromB] = bfs(endpointB);
49
50        // The diameter length is the distance between endpointA and endpointB.
51        int diameter = distFromA[endpointB];
52
53        // A node is "special" if it is a diameter endpoint, i.e. its distance
54        // from one of the two endpoints equals the full diameter length.
55        string answer(n, '0');
56        for (int i = 0; i < n; ++i) {
57            if (distFromA[i] == diameter || distFromB[i] == diameter) {
58                answer[i] = '1';
59            }
60        }
61        return answer;
62    }
63};
64

1/**
2 * Finds the "special" nodes in a tree.
3 *
4 * A node is considered special if it can be one of the two endpoints of some
5 * diameter (a longest path) of the tree. We detect this by:
6 *   1. Running BFS from an arbitrary node to find one endpoint `a` of a diameter.
7 *   2. Running BFS from `a` to find the opposite endpoint `b` and distances `dist1`.
8 *   3. Running BFS from `b` to obtain distances `dist2`.
9 *   4. The diameter length is `d = dist1[b]`. Any node whose distance to either
10 *      endpoint equals `d` is itself a diameter endpoint, hence "special".
11 *
12 * @param n     The number of nodes in the tree (labeled 0..n-1).
13 * @param edges The undirected edges of the tree.
14 * @returns     A binary string where index `i` is '1' if node `i` is special, else '0'.
15 */
16function findSpecialNodes(n: number, edges: number[][]): string {
17    // Build the adjacency list for the undirected tree.
18    const graph: number[][] = Array.from({ length: n }, () => []);
19    for (const [from, to] of edges) {
20        graph[from].push(to);
21        graph[to].push(from);
22    }
23
24    /**
25     * Breadth-first search from `start`.
26     *
27     * @param start The source node.
28     * @returns A tuple `[farthest, distances]` where `farthest` is the node
29     *          with the greatest distance from `start`, and `distances` holds
30     *          the shortest distance from `start` to every node.
31     */
32    const bfs = (start: number): [number, number[]] => {
33        const distances: number[] = new Array<number>(n).fill(-1);
34        distances[start] = 0;
35
36        // Use the queue as a growing array; iterate as we discover new nodes.
37        const queue: number[] = [start];
38        let farthest = start;
39
40        for (const current of queue) {
41            // Track the node lying farthest from `start`.
42            if (distances[current] > distances[farthest]) {
43                farthest = current;
44            }
45            // Visit all unvisited neighbors.
46            for (const neighbor of graph[current]) {
47                if (distances[neighbor] === -1) {
48                    distances[neighbor] = distances[current] + 1;
49                    queue.push(neighbor);
50                }
51            }
52        }
53
54        return [farthest, distances];
55    };
56
57    // Step 1: From node 0, find one endpoint `endpointA` of a diameter.
58    const [endpointA] = bfs(0);
59
60    // Step 2: From `endpointA`, find the opposite endpoint `endpointB`
61    //         and the distances from `endpointA`.
62    const [endpointB, distFromA] = bfs(endpointA);
63
64    // Step 3: From `endpointB`, compute distances to every node.
65    const [, distFromB] = bfs(endpointB);
66
67    // The diameter length is the distance between the two endpoints.
68    const diameter = distFromA[endpointB];
69
70    // Step 4: Mark every node that is itself a diameter endpoint.
71    const answer: string[] = new Array<string>(n).fill('0');
72    for (let i = 0; i < n; i++) {
73        if (distFromA[i] === diameter || distFromB[i] === diameter) {
74            answer[i] = '1';
75        }
76    }
77
78    return answer.join('');
79}
80