# Time Taken to Mark All Nodes
**Difficulty:** HARD
[External](https://leetcode.com/problems/time-taken-to-mark-all-nodes)
Canonical: https://scaleengineer.com/dsa/problems/time-taken-to-mark-all-nodes
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Graph
---
## Problem
There exists an **undirected** tree with `n` nodes numbered `0` to `n - 1`. You are given a 2D integer array `edges` of length `n - 1`, where `edges[i] = [ui, vi]` indicates that there is an edge between nodes `ui` and `vi` in the tree.

Initially, **all** nodes are **unmarked**. For each node `i`:

* If `i` is odd, the node will get marked at time `x` if there is **at least** one node _adjacent_ to it which was marked at time `x - 1`.
* If `i` is even, the node will get marked at time `x` if there is **at least** one node _adjacent_ to it which was marked at time `x - 2`.

Return an array `times` where `times[i]` is the time when all nodes get marked in the tree, if you mark node `i` at time `t = 0`.

**Note** that the answer for each `times[i]` is **independent**, i.e. when you mark node `i` all other nodes are _unmarked_.

**Example 1:**

**Input:** edges = \[\[0,1\],\[0,2\]\]

**Output:** \[2,4,3\]

**Explanation:**

![](https://assets.glich.co/dsa/time-taken-to-mark-all-nodes/image0.png)

* For `i = 0`:  
  * Node 1 is marked at `t = 1`, and Node 2 at `t = 2`.
* For `i = 1`:  
  * Node 0 is marked at `t = 2`, and Node 2 at `t = 4`.
* For `i = 2`:  
  * Node 0 is marked at `t = 2`, and Node 1 at `t = 3`.

**Example 2:**

**Input:** edges = \[\[0,1\]\]

**Output:** \[1,2\]

**Explanation:**

![](https://assets.glich.co/dsa/time-taken-to-mark-all-nodes/image1.png)

* For `i = 0`:  
  * Node 1 is marked at `t = 1`.
* For `i = 1`:  
  * Node 0 is marked at `t = 2`.

**Example 3:**

**Input:** edges = \[\[2,4\],\[0,1\],\[2,3\],\[0,2\]\]

**Output:** \[4,6,3,5,5\]

**Explanation:**

![](https://assets.glich.co/dsa/time-taken-to-mark-all-nodes/image2.png)

**Constraints:**

* `2 <= n <= 105`
* `edges.length == n - 1`
* `edges[i].length == 2`
* `0 <= edges[i][0], edges[i][1] <= n - 1`
* The input is generated such that `edges` represents a valid tree.

# Approaches
## Brute-Force Simulation for Each Starting Node
The most straightforward way to solve this problem is to simulate the marking process for each possible starting node. For each node `i` from `0` to `n-1`, we treat it as the initial node marked at time `t=0` and calculate the time it takes for every other node in the tree to get marked. The final answer for `i` is the maximum of these times.
**Time:** O(N^2). For each of the `N` starting nodes, we perform a 0-1 BFS which takes `O(N + E)` time, where `E` is the number of edges. Since it's a tree, `E = N-1`, so one BFS is `O(N)`. The total time is `N * O(N) = O(N^2)`. · **Space:** O(N). We need `O(N)` space for the adjacency list, `O(N)` for the `dist` array, and `O(N)` for the deque in the worst case.
**Pros:** Relatively simple to understand as it directly models the problem.; Correctly solves the problem for smaller inputs.
**Cons:** The `O(N^2)` complexity is too slow for the given constraints (`N` up to 10^5), leading to a "Time Limit Exceeded" error.
### Explanation
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.
```java
import java.util.*;

class Solution {
    public int[] timeTaken(int[][] edges) {
        int n = edges.length + 1;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = calculateMaxTime(i, n, adj);
        }
        return result;
    }

    private int calculateMaxTime(int startNode, int n, List<List<Integer>> adj) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[startNode] = 0;

        Deque<Integer> deque = new ArrayDeque<>();
        deque.addFirst(startNode);

        int maxTime = 0;

        while (!deque.isEmpty()) {
            int u = deque.pollFirst();
            maxTime = Math.max(maxTime, dist[u]);

            for (int v : adj.get(u)) {
                int cost = (v % 2 == 0) ? 2 : 1;
                if (dist[u] != Integer.MAX_VALUE && dist[u] + cost < dist[v]) {
                    dist[v] = dist[u] + cost;
                    if (cost == 1) {
                        deque.addFirst(v);
                    } else {
                        deque.addLast(v);
                    }
                }
            }
        }
        return maxTime;
    }
}
```
### Algorithm
*   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`.

## Dynamic Programming on Tree with Rerooting
A much more efficient approach is to use dynamic programming on the tree, often known as the "rerooting" technique. Instead of re-calculating from scratch for each starting node, we can compute the answer for all nodes in just two passes (DFS traversals) over the tree.
**Time:** O(N). Both DFS traversals visit each node and edge once. The prefix/suffix maximum calculations for children of a node `u` take time proportional to its degree. The sum of degrees in a tree is `2(N-1)`, so the total time for these calculations across all nodes is `O(N)`. · **Space:** O(N). We need `O(N)` space for the adjacency list, `down`, `up` arrays, and the recursion stack in the worst case (for a skewed tree). The prefix/suffix arrays are local to the function call and their maximum size is bounded by the maximum degree, which can be up to `N-1`.
**Pros:** Highly efficient with linear time complexity.; The optimal solution for the given constraints.
**Cons:** The logic is more complex and less intuitive than the brute-force approach.; Implementation requires careful handling of tree traversals and DP state transitions.
### Explanation
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`.
```java
import java.util.*;

class Solution {
    private List<List<Integer>> adj;
    private int[] cost;
    private int[] down;
    private int[] up;
    private int n;

    public int[] timeTaken(int[][] edges) {
        n = edges.length + 1;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        cost = new int[n];
        for (int i = 0; i < n; i++) {
            cost[i] = (i % 2 == 0) ? 2 : 1;
        }

        down = new int[n];
        up = new int[n];

        // First DFS to compute `down` values
        dfs1(0, -1);

        // Second DFS to compute `up` values
        dfs2(0, -1);

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = Math.max(down[i], up[i]);
        }
        return result;
    }

    private void dfs1(int u, int p) {
        down[u] = 0;
        for (int v : adj.get(u)) {
            if (v == p) continue;
            dfs1(v, u);
            down[u] = Math.max(down[u], cost[v] + down[v]);
        }
    }

    private void dfs2(int u, int p) {
        List<Integer> children = new ArrayList<>();
        for (int v : adj.get(u)) {
            if (v != p) {
                children.add(v);
            }
        }

        int k = children.size();
        if (k == 0) return;

        int[] prefixMax = new int[k];
        int[] suffixMax = new int[k];

        prefixMax[0] = cost[children.get(0)] + down[children.get(0)];
        for (int i = 1; i < k; i++) {
            prefixMax[i] = Math.max(prefixMax[i - 1], cost[children.get(i)] + down[children.get(i)]);
        }

        suffixMax[k - 1] = cost[children.get(k - 1)] + down[children.get(k - 1)];
        for (int i = k - 2; i >= 0; i--) {
            suffixMax[i] = Math.max(suffixMax[i + 1], cost[children.get(i)] + down[children.get(i)]);
        }

        for (int i = 0; i < k; i++) {
            int v = children.get(i);
            int siblingMax = 0;
            if (i > 0) {
                siblingMax = Math.max(siblingMax, prefixMax[i - 1]);
            }
            if (i < k - 1) {
                siblingMax = Math.max(siblingMax, suffixMax[i + 1]);
            }
            
            up[v] = cost[u] + Math.max(up[u], siblingMax);
            dfs2(v, u);
        }
    }
}
```
### Algorithm
*   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])`.