Longest special path

Array Hash Table Tree Depth-First Search Prefix Sum

22.4% acceptance

Feb 25, 2026

126

You are given an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1, represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi, lengthi] indicates an edge between nodes ui and vi with length lengthi. You are also given an integer array nums, where nums[i] represents the value at node i. A special path is defined as a downward path from an ancestor node to a descendant node such that all the values of the nodes in that path are unique. Note that a path may start and end at the same node. Return an array result of size 2, where result[0] is the length of the longest special path, and result[1] is the minimum number of nodes in all possible longest special paths.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn longest_special_path(edges: Vec<Vec<i32>>, nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    let mut adj: Vec<Vec<(usize, i32)>> = vec![vec![]; n];
    for e in &edges {
      let u = e[0] as usize;
      let v = e[1] as usize;
      let w = e[2];
      adj[u].push((v, w));
      adj[v].push((u, w));
    }
    // DFS: track path from root, prefix sum of lengths, last occurrence of each value
    let mut best_len = 0i32;
    let mut best_nodes = 1i32;
    // last_seen[val] = depth (index in path) of last occurrence of val, or -1
    let mut last_seen = vec![-1i32; 50001];
    // prefix[i] = distance from root to node at depth i
    let mut prefix = vec![0i64; n + 1];
    // path_vals[i] = value of node at depth i
    let mut path_vals = vec![0usize; n + 1];
    fn dfs(
      u: usize, parent: usize, depth: usize,
      adj: &Vec<Vec<(usize, i32)>>, nums: &Vec<i32>,
      last_seen: &mut Vec<i32>, prefix: &mut Vec<i64>,
      path_vals: &mut Vec<usize>,
      best_len: &mut i32, best_nodes: &mut i32,
      min_start: usize, // earliest valid start depth
    ) {
      let val = nums[u] as usize;
      let new_min_start = if last_seen[val] >= 0 {
        (last_seen[val] as usize + 1).max(min_start)
      } else {
        min_start
      };
      let old_last = last_seen[val];
      last_seen[val] = depth as i32;
      path_vals[depth] = val;
      // Special path from depth new_min_start to depth (inclusive)
      let path_len = (prefix[depth] - prefix[new_min_start]) as i32;
      let node_count = (depth - new_min_start + 1) as i32;
      if path_len > *best_len || (path_len == *best_len && node_count < *best_nodes) {
        *best_len = path_len;
        *best_nodes = node_count;
      }
      for &(v, w) in &adj[u] {
        if v == parent { continue; }
        prefix[depth + 1] = prefix[depth] + w as i64;
        dfs(v, u, depth + 1, adj, nums, last_seen, prefix, path_vals,
          best_len, best_nodes, new_min_start);
      }
      last_seen[val] = old_last;
    }
    dfs(0, n, 0, &adj, &nums, &mut last_seen, &mut prefix, &mut path_vals,
      &mut best_len, &mut best_nodes, 0);
    vec![best_len, best_nodes]
  }
}