Time taken to mark all nodes

Dynamic Programming Tree Depth-First Search Graph Theory

27.6% acceptance

Feb 25, 2026

139

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn time_taken(edges: Vec<Vec<i32>>) -> Vec<i32> {
    let n = edges.len() + 1;
    let mut adj = vec![vec![]; n];
    for e in &edges {
      adj[e[0] as usize].push(e[1] as usize);
      adj[e[1] as usize].push(e[0] as usize);
    }

    // Root tree at 0 via BFS, compute parent and BFS order
    let mut parent = vec![n; n]; // n = sentinel "no parent"
    let mut order = Vec::with_capacity(n);
    {
      let mut q = std::collections::VecDeque::new();
      q.push_back(0usize);
      parent[0] = n; // root sentinel
      while let Some(v) = q.pop_front() {
        order.push(v);
        for &u in &adj[v] {
          if parent[u] == n && u != 0 {
            parent[u] = v;
            q.push_back(u);
          }
        }
      }
    }

    // cost(v) = time for node v to get marked once its neighbor is marked
    // odd v → 1 step, even v → 2 steps
    let cost = |v: usize| -> i32 { if v % 2 == 1 { 1 } else { 2 } };

    // down[v] = max time to mark deepest node in subtree of v (starting from v)
    let mut down = vec![0i32; n];
    for &v in order.iter().rev() {
      for &u in &adj[v] {
        if parent[u] == v {
          down[v] = down[v].max(cost(u) + down[u]);
        }
      }
    }

    // Rerooting: up[v] = max time to mark any node NOT in subtree of v (going upward from v)
    let mut up = vec![0i32; n];
    for &v in &order {
      // Track top-2 (cost(c)+down[c]) over children c of v
      let mut top = [(0i32, n); 2]; // (value, child_index)
      for &u in &adj[v] {
        if parent[u] == v {
          let val = cost(u) + down[u];
          if val > top[0].0 {
            top[1] = top[0];
            top[0] = (val, u);
          } else if val > top[1].0 {
            top[1] = (val, u);
          }
        }
      }
      // Compute up[u] for each child u of v
      for &u in &adj[v] {
        if parent[u] == v {
          // Best among v's subtrees excluding u
          let best_excl = if top[0].1 != u { top[0].0 } else { top[1].0 };
          // Going from u up to v costs cost(v)
          up[u] = cost(v) + up[v].max(best_excl);
        }
      }
    }

    (0..n).map(|v| down[v].max(up[v])).collect()
  }
}