Time Taken to Mark All Nodes

• For each node i from 0 to n-1:
  • Initialize dist array of size n with infinity, dist[i] = 0.
  • Create a deque and add i to it.
  • While deque is not empty:
    • Pop node u from the front.
    • For each neighbor v of u:
      • Calculate cost = (v % 2 == 0) ? 2 : 1.
      • If dist[u] + cost < dist[v]:
        • Update dist[v] = dist[u] + cost.
        • If cost == 1, add v to the front of the deque.
        • Else, add v to the back.
  • Find the maximum value in the dist array and store it as the result for starting node i.

The problem of finding the time each node gets marked, given a starting node, can be modeled as a shortest path problem on a graph. The nodes of the graph are the nodes of the tree. The time it takes for a mark to propagate from a node u to an adjacent node v can be seen as the weight of a directed edge from u to v. This weight depends on the destination node v:

• If v is odd, the time delay is 1.
• If v is even, the time delay is 2.

Since the edge weights are small positive integers (1 and 2), we can find the shortest path from a starting node s to all other nodes efficiently using a variation of Breadth-First Search (BFS), often called 0-1 BFS, which uses a deque instead of a standard queue.

The overall algorithm is as follows:

1. Build an adjacency list representation of the tree from the edges input.
2. Initialize an answer array times of size n.
3. Loop through each node i from 0 to n-1: a. Perform a 0-1 BFS starting from node i to calculate the shortest time (dist[j]) for every other node j to be marked. b. The dist array is initialized with infinity, and dist[i] is set to 0. c. A deque is used to store nodes to visit. Initially, it contains i. d. While the deque is not empty, extract a node u. For each neighbor v, calculate the new time dist[u] + cost(v). If this is a shorter path to v, update dist[v] and add v to the deque: to the front if the cost was 1, and to the back if the cost was 2. e. After the BFS completes, find the maximum value in the dist array. This is the time when all nodes are marked. f. Store this maximum time in times[i].
4. Return the times array.

This approach is correct but inefficient because it repeatedly calculates shortest paths over the same tree structure.

1import java.util.*;2 3class Solution {4    public int[] timeTaken(int[][] edges) {5        int n = edges.length + 1;6        List<List<Integer>> adj = new ArrayList<>();7        for (int i = 0; i < n; i++) {8            adj.add(new ArrayList<>());9        }10        for (int[] edge : edges) {11            adj.get(edge[0]).add(edge[1]);12            adj.get(edge[1]).add(edge[0]);13        }14 15        int[] result = new int[n];16        for (int i = 0; i < n; i++) {17            result[i] = calculateMaxTime(i, n, adj);18        }19        return result;20    }21 22    private int calculateMaxTime(int startNode, int n, List<List<Integer>> adj) {23        int[] dist = new int[n];24        Arrays.fill(dist, Integer.MAX_VALUE);25        dist[startNode] = 0;26 27        Deque<Integer> deque = new ArrayDeque<>();28        deque.addFirst(startNode);29 30        int maxTime = 0;31 32        while (!deque.isEmpty()) {33            int u = deque.pollFirst();34            maxTime = Math.max(maxTime, dist[u]);35 36            for (int v : adj.get(u)) {37                int cost = (v % 2 == 0) ? 2 : 1;38                if (dist[u] != Integer.MAX_VALUE && dist[u] + cost < dist[v]) {39                    dist[v] = dist[u] + cost;40                    if (cost == 1) {41                        deque.addFirst(v);42                    } else {43                        deque.addLast(v);44                    }45                }46            }47        }48        return maxTime;49    }50}