Longest Special Path
Source: leetcode
Difficulty: Hard
Tags: array, hash-table, tree, depth-first-search, sliding-window

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.


 


**Example 1:**



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


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


**Explanation:**


#### In the image below, nodes are colored by their corresponding values in `nums`


![](https://assets.leetcode.com/uploads/2024/11/02/tree3.jpeg)


The longest special paths are `2 -> 5` and `0 -> 1 -> 4`, both having a length of 6\. The minimum number of nodes across all longest special paths is 2\.



**Example 2:**



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


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


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/11/02/tree4.jpeg)


The longest special paths are `0` and `1`, both having a length of 0\. The minimum number of nodes across all longest special paths is 1\.



 


**Constraints:**


- `2 <= n <= 5 * 104`
- `edges.length == n - 1`
- `edges[i].length == 3`
- `0 <= ui, vi < n`
- `1 <= lengthi <= 103`
- `nums.length == n`
- `0 <= nums[i] <= 5 * 104`
- The input is generated such that `edges` represents a valid tree.




C++ solution:
class Solution {
public:
    vector<int> longestSpecialPath(vector<vector<int>>& edges, vector<int>& nums) {
        int n = nums.size();
        vector<vector<pair<int,int>>> graph(n);
        for(auto &e : edges){
            int u = e[0], v = e[1], w = e[2];
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }
        vector<int> cum(n, 0);
        vector<int> lastOccurrence(50001, -1);
        int bestSum = 0, bestCount = 1;
        function<void(int,int,int,int)> dfs = [&](int node, int parent, int depth, int curStart) {
            int val = nums[node];
            int prev = lastOccurrence[val];
            int newStart = max(curStart, (prev == -1 ? 0 : prev + 1));
            int candidate = cum[depth] - (newStart == 0 ? 0 : cum[newStart]);
            int count = depth - newStart + 1;
            if(candidate > bestSum) { bestSum = candidate; bestCount = count; }
            else if(candidate == bestSum) { bestCount = min(bestCount, count); }
            int oldVal = lastOccurrence[val];
            lastOccurrence[val] = depth;
            for(auto &edge : graph[node]){
                int nxt = edge.first, w = edge.second;
                if(nxt == parent) continue;
                cum[depth+1] = cum[depth] + w;
                dfs(nxt, node, depth+1, newStart);
            }
            lastOccurrence[val] = oldVal;
        };
        dfs(0, -1, 0, 0);
        return {bestSum, bestCount};
    }
};

Go solution:
func longestSpecialPath(edges [][]int, nums []int) []int {
	n := len(nums)
	type Edge struct {
		to int
		w  int
	}
	graph := make([][]Edge, n)
	for i := 0; i < len(edges); i++ {
		u, v, w := edges[i][0], edges[i][1], edges[i][2]
		graph[u] = append(graph[u], Edge{v, w})
		graph[v] = append(graph[v], Edge{u, w})
	}
	bestLen, bestNodes := 0, 1
	cum := make([]int, n+1)
	used := make(map[int]int)
	var dfs func(v, parent, curStart, depth, curCum int)
	dfs = func(v, parent, curStart, depth, curCum int) {
		cum[depth] = curCum
		curLength := curCum - cum[curStart]
		numNodes := depth - curStart + 1
		if curLength > bestLen {
			bestLen = curLength
			bestNodes = numNodes
		} else if curLength == bestLen && numNodes < bestNodes {
			bestNodes = numNodes
		}
		for _, e := range graph[v] {
			if e.to == parent {
				continue
			}
			newCum := curCum + e.w
			newDepth := depth + 1
			newStart := curStart
			val := nums[e.to]
			if pos, ok := used[val]; ok && pos >= newStart {
				if pos+1 > newStart {
					newStart = pos + 1
				}
			}
			prev, exist := used[val]
			used[val] = newDepth
			dfs(e.to, v, newStart, newDepth, newCum)
			if exist {
				used[val] = prev
			} else {
				delete(used, val)
			}
		}
	}
	used[nums[0]] = 0
	dfs(0, -1, 0, 0, 0)
	return []int{bestLen, bestNodes}
}

Java solution:
class Solution {
    int globalMax;
    int globalMin;
    int[] lastOccurrence;
    int[] pathSum;
    int[] nums;
    public int[] longestSpecialPath(int[][] edges, int[] nums) {
        int n = nums.length;
        this.nums = nums;
        @SuppressWarnings("unchecked")
        ArrayList<Edge>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            graph[u].add(new Edge(v, w));
            graph[v].add(new Edge(u, w));
        }
        @SuppressWarnings("unchecked")
        ArrayList<Edge>[] children = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            children[i] = new ArrayList<>();
        }
        buildTree(0, -1, graph, children);
        globalMax = 0;
        globalMin = Integer.MAX_VALUE;
        lastOccurrence = new int[50001];
        for (int i = 0; i < 50001; i++) {
            lastOccurrence[i] = -1;
        }
        pathSum = new int[n];
        dfs(0, 0, 0, 0, children);
        return new int[]{globalMax, globalMin};
    }
    void dfs(int node, int depth, int curSum, int windowStart, ArrayList<Edge>[] children) {
        int val = nums[node];
        int oldOccurrence = lastOccurrence[val];
        int newWindowStart = windowStart;
        if (oldOccurrence >= windowStart) {
            newWindowStart = oldOccurrence + 1;
        }
        lastOccurrence[val] = depth;
        pathSum[depth] = curSum;
        int candidate = curSum - pathSum[newWindowStart];
        int candidateCount = depth - newWindowStart + 1;
        if (candidate > globalMax) {
            globalMax = candidate;
            globalMin = candidateCount;
        } else if (candidate == globalMax) {
            if (candidateCount < globalMin) globalMin = candidateCount;
        }
        for (Edge edge : children[node]) {
            dfs(edge.child, depth + 1, curSum + edge.weight, newWindowStart, children);
        }
        lastOccurrence[val] = oldOccurrence;
    }
    void buildTree(int node, int parent, ArrayList<Edge>[] graph, ArrayList<Edge>[] children) {
        for (Edge edge : graph[node]) {
            if (edge.child != parent) {
                children[node].add(new Edge(edge.child, edge.weight));
                buildTree(edge.child, node, graph, children);
            }
        }
    }
    class Edge {
        int child;
        int weight;
        Edge(int child, int weight) {
            this.child = child;
            this.weight = weight;
        }
    }
}

JavaScript solution:
/**
 * @param {number[][]} edges
 * @param {number[]} nums
 * @return {number[]}
 */
var longestSpecialPath = function(edges, nums) {
  const n = nums.length;
  const graph = new Array(n);
  for (let i = 0; i < n; i++) graph[i] = [];
  for (const [u, v, w] of edges) {
    graph[u].push([v, w]);
    graph[v].push([u, w]);
  }
  let bestLen = 0, bestCount = Infinity;
  const dp = new Array(n + 1).fill(0);
  const occ = new Map();
  function dfs(node, parent, depth, winStart) {
    const val = nums[node];
    const old = occ.has(val) ? occ.get(val) : undefined;
    let newWinStart = winStart;
    if (old !== undefined && old >= winStart) newWinStart = old + 1;
    occ.set(val, depth);
    const curLen = dp[depth] - dp[newWinStart];
    const curCount = depth - newWinStart + 1;
    if (curLen > bestLen) {
      bestLen = curLen;
      bestCount = curCount;
    } else if (curLen === bestLen && curCount < bestCount) {
      bestCount = curCount;
    }
    for (const [nbr, wt] of graph[node]) {
      if (nbr === parent) continue;
      dp[depth + 1] = dp[depth] + wt;
      dfs(nbr, node, depth + 1, newWinStart);
    }
    if (occ.get(val) === depth) {
      if (old !== undefined) occ.set(val, old);
      else occ.delete(val);
    }
  }
  dfs(0, -1, 0, 0);
  return [bestLen, bestCount];
};

Python solution:
class Solution:
    def longestSpecialPath(self, edges: List[List[int]], nums: List[int]) -> List[int]:
        sys.setrecursionlimit(10**6)
        n = len(nums)
        graph = [[] for _ in range(n)]
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        best_sum = 0
        best_cnt = 10**9
        lastOcc = {}
        path_cum = [0]
        def dfs(node, parent, win):
            nonlocal best_sum, best_cnt
            level = len(path_cum) - 1
            v = nums[node]
            prev = lastOcc.get(v, None)
            new_win = win if prev is None else max(win, prev + 1)
            lastOcc[v] = level
            cur = path_cum[-1]
            cand = cur - path_cum[new_win]
            cnt = level - new_win + 1
            if cand > best_sum:
                best_sum = cand
                best_cnt = cnt
            elif cand == best_sum and cnt < best_cnt:
                best_cnt = cnt
            for nei, w in graph[node]:
                if nei == parent:
                    continue
                path_cum.append(cur + w)
                dfs(nei, node, new_win)
                path_cum.pop()
            if prev is None:
                del lastOcc[v]
            else:
                lastOcc[v] = prev
        dfs(0, -1, 0)
        return [best_sum, best_cnt]

Ruby solution:
def longest_special_path(edges, nums)
  n = nums.size
  graph = Array.new(n){ [] }
  edges.each do |u, v, w|
    graph[u] << [v, w]
    graph[v] << [u, w]
  end
  @best_length = 0
  @best_count = Float::INFINITY
  ps = []
  ps.push(0)
  last_occ = {}
  last_occ[nums[0]] = 0
  dfs = lambda do |node, parent, win, depth, cum|
    cur_length = cum - ps[win]
    cur_count = depth - win + 1
    if cur_length > @best_length
      @best_length = cur_length
      @best_count = cur_count
    elsif cur_length == @best_length && cur_count < @best_count
      @best_count = cur_count
    end
    graph[node].each do |nxt, w|
      next if nxt == parent
      new_cum = cum + w
      new_depth = depth + 1
      new_win = win
      val = nums[nxt]
      if last_occ.key?(val)
        new_win = [new_win, last_occ[val] + 1].max
      end
      old = last_occ[val]
      last_occ[val] = new_depth
      ps.push(new_cum)
      dfs.call(nxt, node, new_win, new_depth, new_cum)
      ps.pop
      if old.nil?
        last_occ.delete(val)
      else
        last_occ[val] = old
      end
    end
  end
  dfs.call(0, -1, 0, 0, 0)
  [@best_length, @best_count]
end