1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    // Adjacency list representation of the graph
7    private List<Integer>[] graph;
8
9    /**
10     * Finds the last marked nodes based on given edges.
11     * 
12     * @param edges The edges of the tree.
13     * @return An array where each element at index `i` is the last marked node
14     *         on the longest path from node `i`.
15     */
16    public int[] lastMarkedNodes(int[][] edges) {
17        int n = edges.length + 1; // Calculate number of nodes
18        graph = new List[n];
19      
20        // Initialize adjacency list for the graph
21        Arrays.setAll(graph, k -> new ArrayList<>());
22      
23        // Populate the adjacency list from edges
24        for (var edge : edges) {
25            int u = edge[0], v = edge[1];
26            graph[u].add(v);
27            graph[v].add(u);
28        }
29      
30        // First DFS to find farthest node from node 0
31        int[] dist1 = new int[n];
32        dist1[0] = 0;
33        dfs(0, -1, dist1);
34        int a = maxNode(dist1); // Node a is the farthest from 0
35      
36        // Second DFS to find farthest node from node a
37        int[] dist2 = new int[n];
38        dist2[a] = 0;
39        dfs(a, -1, dist2);
40        int b = maxNode(dist2); // Node b is the farthest from a
41      
42        // Third DFS to get distances from node b
43        int[] dist3 = new int[n];
44        dist3[b] = 0;
45        dfs(b, -1, dist3);
46      
47        // Determine the last marked node on the longest path from each node
48        int[] result = new int[n];
49        for (int i = 0; i < n; i++) {
50            result[i] = dist2[i] > dist3[i] ? a : b;
51        }
52        return result;
53    }
54
55    /**
56     * Depth First Search to calculate distances from a given start node.
57     * 
58     * @param currentNode The current node being visited.
59     * @param parentNode The parent node of the current node.
60     * @param distances Distance array to the start node.
61     */
62    private void dfs(int currentNode, int parentNode, int[] distances) {
63        for (int neighbor : graph[currentNode]) {
64            if (neighbor != parentNode) {
65                distances[neighbor] = distances[currentNode] + 1; // Increase distance
66                dfs(neighbor, currentNode, distances);
67            }
68        }
69    }
70
71    /**
72     * Finds the index of the node with the maximum distance.
73     * 
74     * @param distances Distance array.
75     * @return Index of the node with the largest distance.
76     */
77    private int maxNode(int[] distances) {
78        int maxIndex = 0;
79        for (int i = 0; i < distances.length; i++) {
80            if (distances[maxIndex] < distances[i]) {
81                maxIndex = i; // Update maxIndex if a larger distance is found
82            }
83        }
84        return maxIndex;
85    }
86}
87

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // This function returns a vector of integers representing the last marked nodes.
7    std::vector<int> lastMarkedNodes(std::vector<std::vector<int>>& edges) {
8        int n = edges.size() + 1; // Calculate the number of nodes
9        graph.resize(n);
10        // Build the adjacency list for the graph
11        for (const auto& edge : edges) {
12            int u = edge[0], v = edge[1];
13            graph[u].push_back(v);
14            graph[v].push_back(u);
15        }
16        std::vector<int> distFromRoot(n);
17        dfs(0, -1, distFromRoot); // Perform DFS to find distances from the root node
18        int nodeA = std::max_element(distFromRoot.begin(), distFromRoot.end()) - distFromRoot.begin();
19
20        std::vector<int> distFromNodeA(n);
21        dfs(nodeA, -1, distFromNodeA); // Perform DFS from node A to find distances
22        int nodeB = std::max_element(distFromNodeA.begin(), distFromNodeA.end()) - distFromNodeA.begin();
23
24        std::vector<int> distFromNodeB(n);
25        dfs(nodeB, -1, distFromNodeB); // Perform DFS from node B to find distances
26
27        std::vector<int> resultNodes;
28        // Determine the result for each node based on distances
29        for (int i = 0; i < n; ++i) {
30            // If the distance from node A is greater choose A, otherwise choose B
31            resultNodes.push_back(distFromNodeA[i] > distFromNodeB[i] ? nodeA : nodeB);
32        }
33        return resultNodes;
34    }
35
36private:
37    std::vector<std::vector<int>> graph; // Adjacency list of the graph
38
39    // Depth First Search to compute distances from a given starting node
40    void dfs(int currentNode, int parentNode, std::vector<int>& distances) {
41        for (int neighbor : graph[currentNode]) {
42            if (neighbor != parentNode) {
43                distances[neighbor] = distances[currentNode] + 1;
44                dfs(neighbor, currentNode, distances);
45            }
46        }
47    }
48};
49

1// Function to find the last marked nodes
2function lastMarkedNodes(edges: number[][]): number[] {
3    // Total number of nodes is one more than the number of edges
4    const n = edges.length + 1;
5
6    // Graph adjacency list initialization
7    const g: number[][] = Array.from({ length: n }, () => []);
8
9    // Building the graph from given edges
10    for (const [u, v] of edges) {
11        g[u].push(v);
12        g[v].push(u);
13    }
14
15    // Depth First Search (DFS) to calculate distances
16    const dfs = (i: number, fa: number, dist: number[]) => {
17        for (const j of g[i]) {
18            if (j !== fa) {
19                dist[j] = dist[i] + 1;
20                dfs(j, i, dist);
21            }
22        }
23    };
24
25    // First DFS to find the furthest node from node 0
26    const dist1: number[] = Array(n).fill(0);
27    dfs(0, -1, dist1);
28
29    // Node 'a' is the furthest from node 0
30    const a = dist1.indexOf(Math.max(...dist1));
31
32    // Second DFS starting from node 'a' to find its furthest node 'b'
33    const dist2: number[] = Array(n).fill(0);
34    dfs(a, -1, dist2);
35
36    // Node 'b' is the furthest from node 'a'
37    const b = dist2.indexOf(Math.max(...dist2));
38
39    // Third DFS starting from node 'b' to compute distances for use in the final decision
40    const dist3: number[] = Array(n).fill(0);
41    dfs(b, -1, dist3);
42
43    // Determine the last marked nodes
44    const ans: number[] = [];
45    for (let i = 0; i < n; ++i) {
46        // Compare distances to decide whether to mark node 'a' or 'b'
47        ans.push(dist2[i] > dist3[i] ? a : b);
48    }
49
50    // Return the array of last marked nodes
51    return ans;
52}
53