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}

• Build an adjacency list for the tree.
• Define cost[i] as 1 for odd i and 2 for even i.
• DFS 1 (post-order, e.g., dfs1(u, p)):
  • For each child v of u, recursively call dfs1(v, u).
  • After recursive calls, calculate down[u] = max(down[u], cost[v] + down[v]) over all children v. Base case for leaves is down[u] = 0.
• DFS 2 (pre-order, e.g., dfs2(u, p)):
  • For node u, calculate the longest path from p into a sibling subtree of u. This can be done efficiently by pre-calculating prefix and suffix maximums of cost[c] + down[c] for all children c of u.
  • Calculate up[v] for each child v: up[v] = cost[u] + max(up[u], sibling_max_path).
  • Recursively call dfs2(v, u) for all children v. Base case for the root is up[root] = 0.
• Combine Results: For each node i, the answer is max(down[i], up[i]).

The core idea is to first root the tree arbitrarily (say, at node 0). Then, for each node u, we calculate two values:

1. down[u]: The longest path (in terms of marking time) starting from u and ending at a node within its subtree.
2. up[u]: The longest path starting from u and ending at a node outside its subtree.

The final answer for a starting node u is simply the maximum of down[u] and up[u].

The algorithm proceeds in two main steps:

Step 1: First DFS (Post-order Traversal)

• We perform a DFS from the root (e.g., node 0). In the post-order traversal phase (after visiting all children), we compute down[u] for each node u.
• The longest path from u into its subtree will either be to u itself (time 0) or will go through one of its children c. The time to reach a node v in c's subtree from u is cost(c) + dist(c, v).
• The recurrence for down[u] is: down[u] = max(0, max_{c ∈ children(u)} {cost(c) + down[c]}).
• cost(c) is 1 if c is odd, 2 if c is even.

Step 2: Second DFS (Pre-order Traversal)

• We perform another DFS from the root. In the pre-order traversal phase (before visiting children), we compute up[u] for each node u.
• up[root] is 0, as there are no nodes outside its "subtree" (the whole tree).
• For any other node u with parent p, a path starting at u and going outside its subtree must first go to p. The time to reach p is cost(p). From p, the path can either continue "upwards" (away from p's subtree) or go into one of u's sibling subtrees.
• The recurrence for up[u] is: up[u] = cost(p) + max(up[p], max_{s ∈ siblings(u)} {cost(s) + down[s]}).
• To efficiently calculate the maximum over siblings for each child, we can use prefix and suffix maximums on the children's cost + down values.

After both DFS traversals, ans[i] = max(down[i], up[i]) for all i.

1import java.util.*;2 3class Solution {4    private List<List<Integer>> adj;5    private int[] cost;6    private int[] down;7    private int[] up;8    private int n;9 10    public int[] timeTaken(int[][] edges) {11        n = edges.length + 1;12        adj = new ArrayList<>();13        for (int i = 0; i < n; i++) {14            adj.add(new ArrayList<>());15        }16        for (int[] edge : edges) {17            adj.get(edge[0]).add(edge[1]);18            adj.get(edge[1]).add(edge[0]);19        }20 21        cost = new int[n];22        for (int i = 0; i < n; i++) {23            cost[i] = (i % 2 == 0) ? 2 : 1;24        }25 26        down = new int[n];27        up = new int[n];28 29        // First DFS to compute `down` values30        dfs1(0, -1);31 32        // Second DFS to compute `up` values33        dfs2(0, -1);34 35        int[] result = new int[n];36        for (int i = 0; i < n; i++) {37            result[i] = Math.max(down[i], up[i]);38        }39        return result;40    }41 42    private void dfs1(int u, int p) {43        down[u] = 0;44        for (int v : adj.get(u)) {45            if (v == p) continue;46            dfs1(v, u);47            down[u] = Math.max(down[u], cost[v] + down[v]);48        }49    }50 51    private void dfs2(int u, int p) {52        List<Integer> children = new ArrayList<>();53        for (int v : adj.get(u)) {54            if (v != p) {55                children.add(v);56            }57        }58 59        int k = children.size();60        if (k == 0) return;61 62        int[] prefixMax = new int[k];63        int[] suffixMax = new int[k];64 65        prefixMax[0] = cost[children.get(0)] + down[children.get(0)];66        for (int i = 1; i < k; i++) {67            prefixMax[i] = Math.max(prefixMax[i - 1], cost[children.get(i)] + down[children.get(i)]);68        }69 70        suffixMax[k - 1] = cost[children.get(k - 1)] + down[children.get(k - 1)];71        for (int i = k - 2; i >= 0; i--) {72            suffixMax[i] = Math.max(suffixMax[i + 1], cost[children.get(i)] + down[children.get(i)]);73        }74 75        for (int i = 0; i < k; i++) {76            int v = children.get(i);77            int siblingMax = 0;78            if (i > 0) {79                siblingMax = Math.max(siblingMax, prefixMax[i - 1]);80            }81            if (i < k - 1) {82                siblingMax = Math.max(siblingMax, suffixMax[i + 1]);83            }84            85            up[v] = cost[u] + Math.max(up[u], siblingMax);86            dfs2(v, u);87        }88    }89}