# Longest Special Path
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-special-path)
Canonical: https://scaleengineer.com/dsa/problems/longest-special-path
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Hash Table, Tree
---
## Problem
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.glich.co/dsa/longest-special-path/image0.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.glich.co/dsa/longest-special-path/image1.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.

# Approaches
## Brute-Force DFS from Each Node
This approach uses a straightforward brute-force method. It considers every node in the tree as a potential starting point for a special path. From each potential start node, it performs a Depth-First Search (DFS) to explore all possible downward paths. During the DFS, it maintains a set of visited node values to ensure the path's 'special' property (unique values). It keeps track of the longest special path found so far and the minimum number of nodes for that length.
**Time:** O(N^2 * D) - In the worst case, we start a DFS from each of the N nodes. Each DFS can traverse a subtree of size up to N. For each node in the path, we do a constant time set operation. The depth D of the recursion can be up to N. A loose upper bound is O(N * N!) but a tighter one is closer to O(N^2 * D), where D is the average depth, making it very slow. · **Space:** O(N) - The space complexity is dominated by the recursion stack depth of the DFS, which can be up to O(N) in the worst case (a skewed tree or line graph). The `visitedValues` set can also store up to O(N) values.
**Pros:** Conceptually simple and easy to follow.; Correctly solves the problem for small inputs.
**Cons:** Extremely inefficient due to redundant computations. Many paths are explored multiple times.; The time complexity is prohibitive for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The algorithm begins by constructing a directed graph or tree structure from the input edges, typically using an adjacency list, to easily traverse from parent to child. Then, it iterates through every node `i` from `0` to `n-1`, treating each as the root of a potential longest special path.

For each starting node `s`, a recursive DFS function is invoked. This function explores all paths downwards from `s`. It takes the current node, the path's length so far, the number of nodes, and a set of the `nums` values encountered on the path as arguments. At each node `u` in the traversal, it checks if `nums[u]` is already in the set of values. If it is, the path is no longer special, and the recursion for this branch stops. Otherwise, it's a valid special path, and we update our global maximum length and corresponding minimum nodes. The process continues by recursively calling the DFS for all children of `u`. Backtracking is used to remove `nums[u]` from the set when returning from the recursion, allowing other paths to be evaluated correctly.

```java
class Solution {
    private List<int[]>[] adj;
    private int[] nums;
    private long maxLength = 0;
    private int minNodes = 1;

    public int[] longestSpecialPath(int[][] edges, int[] nums) {
        int n = nums.length;
        this.nums = nums;
        this.adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(new int[]{edge[1], edge[2]});
            adj[edge[1]].add(new int[]{edge[0], edge[2]});
        }

        // Create a directed tree for downward traversal
        List<int[]>[] directedAdj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            directedAdj[i] = new ArrayList<>();
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        visited[0] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int[] edge : adj[u]) {
                int v = edge[0];
                if (!visited[v]) {
                    visited[v] = true;
                    directedAdj[u].add(edge);
                    q.add(v);
                }
            }
        }
        this.adj = directedAdj;

        for (int i = 0; i < n; i++) {
            dfs(i, 0, 1, new HashSet<>());
        }

        return new int[]{(int)maxLength, minNodes};
    }

    private void dfs(int u, long currentLength, int numNodes, Set<Integer> visitedValues) {
        if (visitedValues.contains(nums[u])) {
            return;
        }

        if (currentLength > maxLength) {
            maxLength = currentLength;
            minNodes = numNodes;
        } else if (currentLength == maxLength) {
            minNodes = Math.min(minNodes, numNodes);
        }

        visitedValues.add(nums[u]);

        for (int[] edge : adj[u]) {
            int v = edge[0];
            int length = edge[1];
            dfs(v, currentLength + length, numNodes + 1, visitedValues);
        }

        visitedValues.remove(nums[u]);
    }
}
```
### Algorithm
*   **Build Adjacency List:** First, convert the `edges` array into an adjacency list representation of the tree, where each entry stores the neighbor and the edge length. Since the problem defines a rooted tree structure with downward paths, we also establish parent-child relationships, for instance, by performing a preliminary Breadth-First Search (BFS) or Depth-First Search (DFS) starting from the root (node 0).
*   **Iterate Through All Start Nodes:** The main idea is to check every possible downward path. A downward path can start at any node in the tree. Therefore, we iterate through each node `s` from `0` to `n-1`, treating it as a potential starting node for a special path.
*   **Depth-First Search for Paths:** For each starting node `s`, we perform a DFS to explore all downward paths originating from it. The DFS function, say `findPaths(u, currentLength, numNodes, visitedValues)`, will traverse the subtree rooted at `u`.
*   **Path Validation and State Update:**
    *   `u`: The current node in the traversal.
    *   `currentLength`: The sum of edge lengths from `s` to `u`'s parent.
    *   `numNodes`: The number of nodes on the path from `s` to `u`'s parent.
    *   `visitedValues`: A `HashSet` to keep track of the `nums` values of nodes on the current path from `s`.
*   **DFS Logic:**
    1.  Inside the `findPaths` function for node `u`, first check if `nums[u]` is already in `visitedValues`. If it is, this path is no longer special, so we terminate this branch of the search.
    2.  If `nums[u]` is unique, we have a valid special path ending at `u`. We compare its length (`currentLength`) and node count (`numNodes`) with the global `maxLength` and `minNodes`, updating them if we've found a new longest path or one with the same length but fewer nodes.
    3.  To explore further down, add `nums[u]` to `visitedValues`.
    4.  Recursively call `findPaths` for all children `v` of `u`, updating the length and node count accordingly: `findPaths(v, currentLength + edge_length(u,v), numNodes + 1, visitedValues)`.
    5.  After the recursive calls for all children return (i.e., after exploring all paths through `u`), backtrack by removing `nums[u]` from `visitedValues` to ensure correctness for other paths in the tree.
*   **Return Result:** After iterating through all possible starting nodes, `maxLength` and `minNodes` will hold the final answer.

## DP on Trees with DSU on Trees (Sack)
A highly efficient solution can be achieved using a form of Dynamic Programming on trees, optimized with the DSU on Trees (also known as Sack) technique. This approach avoids the redundant computations of the brute-force method by processing the tree in a post-order traversal and cleverly merging results from subtrees.

The core of this method is a DFS function that, for each node `u`, computes a map of the longest special paths starting at `u`. To handle the uniqueness constraint efficiently, we use an auxiliary data structure—a map of stacks (`valToNodeStack`). This structure helps to quickly identify if extending a path from a child with its parent `u` would violate the uniqueness constraint by introducing a duplicate `nums[u]` value. The DSU on Trees optimization ensures that we only do full computations for smaller subtrees (light children) and merge their results into the already computed results of the largest subtree (heavy child), bringing the overall complexity down significantly.
**Time:** O(N log N) - Preprocessing (DFS for sizes, tin/tout) takes O(N). The main `dfs_sack` function processes each node. Due to the DSU on Trees heuristic, each node's information is merged into its parent's map. A node is part of a light child's subtree O(log N) times. Each merge operation takes time proportional to the size of the light child's map. The total time complexity for the Sack part is O(N log N). · **Space:** O(N) - The space complexity is determined by the adjacency list, recursion stack, and the maps used in the Sack algorithm. The total size of all maps at any point in the recursion is bounded by O(N). The `valToNodeStack` also stores at most O(N) elements in total across all stacks.
**Pros:** Highly efficient and passes within the time limits for large inputs.; Solves the problem in a single pass over the tree after preprocessing.
**Cons:** Significantly more complex to understand and implement correctly than the brute-force approach.; The logic for merging maps and checking for blockers requires careful handling of pointers and data structures.
### Explanation
This advanced approach combines several techniques. First, we preprocess the tree to determine subtree sizes and `tin`/`tout` times for O(1) ancestor checks. The main algorithm is a recursive DFS that implements the DSU on Trees (Sack) heuristic.

The state passed up during the post-order traversal from a node `u` is a map. This map, `M_u`, keys on a node value `v` and stores a tuple `{length, nodes, end_node}` representing the longest special path that starts at `u` and ends at a descendant `end_node` having `nums[end_node] == v`.

At a node `u`, the algorithm first recursively calls itself on all its 'light' children (children with smaller subtrees) and discards their returned maps. Then, it calls itself on its 'heavy' child and reuses its map. This map is then updated: for each path starting at the heavy child, we check if it can be extended by `u`. This check is the crucial part. We use a global map of stacks, `valToNodeStack`, where `valToNodeStack[v]` contains all nodes on the current path from the root with value `v`. If the highest node on this stack is in the heavy child's subtree, the path is blocked. Otherwise, we extend the path, update its length/nodes, and update the global answer. We then add the path for `u` itself. Finally, we iterate through the light children again, compute their maps, and merge their valid paths into `u`'s map. This merging of smaller maps into a larger one is what gives DSU on Trees its efficiency.

```java
class Solution {
    private List<int[]>[] adj;
    private int[] nums;
    private int[] subtreeSize;
    private int[] tin, tout;
    private int timer;
    private long maxLength = 0;
    private int minNodes = 1;
    private Map<Integer, Deque<Integer>> valToNodeStack = new HashMap<>();
    private Map<Integer, PathInfo>[] maps;

    static class PathInfo {
        long length;
        int nodes;
        int endNode;

        PathInfo(long length, int nodes, int endNode) {
            this.length = length;
            this.nodes = nodes;
            this.endNode = endNode;
        }
    }

    public int[] longestSpecialPath(int[][] edges, int[] nums) {
        int n = nums.length;
        this.nums = nums;
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] edge : edges) {
            adj[edge[0]].add(new int[]{edge[1], edge[2]});
            adj[edge[1]].add(new int[]{edge[0], edge[2]});
        }

        subtreeSize = new int[n];
        tin = new int[n];
        tout = new int[n];
        maps = new HashMap[n];

        // Pre-computation DFS
        dfs_size(0, -1);
        // Main DFS with Sack
        dfs_sack(0, -1);

        return new int[]{(int)maxLength, minNodes};
    }

    private void dfs_size(int u, int p) {
        tin[u] = timer++;
        subtreeSize[u] = 1;
        List<int[]> children = new ArrayList<>();
        for (int[] edge : adj[u]) {
            int v = edge[0];
            if (v != p) {
                children.add(edge);
                dfs_size(v, u);
                subtreeSize[u] += subtreeSize[v];
            }
        }
        adj[u] = children;
        tout[u] = timer++;
    }

    private boolean isAncestor(int u, int v) {
        if (u == -1 || v == -1) return false;
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }

    private void updateGlobal(long len, int nodes) {
        if (len > maxLength) {
            maxLength = len;
            minNodes = nodes;
        } else if (len == maxLength) {
            minNodes = Math.min(minNodes, nodes);
        }
    }

    private void dfs_sack(int u, int p) {
        valToNodeStack.computeIfAbsent(nums[u], k -> new ArrayDeque<>()).push(u);

        int heavyChild = -1, maxSubtree = -1;
        for (int[] edge : adj[u]) {
            int v = edge[0];
            if (subtreeSize[v] > maxSubtree) {
                maxSubtree = subtreeSize[v];
                heavyChild = v;
            }
        }

        for (int[] edge : adj[u]) {
            int v = edge[0];
            if (v != heavyChild) {
                dfs_sack(v, u);
            }
        }

        if (heavyChild != -1) {
            dfs_sack(heavyChild, u);
            maps[u] = maps[heavyChild];
        } else {
            maps[u] = new HashMap<>();
        }

        // Merge logic
        // Process paths from heavy child
        int u_val = nums[u];
        int blockerNode = valToNodeStack.get(u_val).size() > 1 ? valToNodeStack.get(u_val).peek() : -1;
        if (valToNodeStack.get(u_val).size() > 1) {
            valToNodeStack.get(u_val).pop();
            blockerNode = valToNodeStack.get(u_val).peek();
            valToNodeStack.get(u_val).push(u);
        }

        List<Integer> toRemove = new ArrayList<>();
        for (Map.Entry<Integer, PathInfo> entry : maps[u].entrySet()) {
            PathInfo pi = entry.getValue();
            if (isAncestor(heavyChild, blockerNode) && isAncestor(blockerNode, pi.endNode)) {
                toRemove.add(entry.getKey());
            } else {
                pi.length += getEdgeLength(u, heavyChild);
                pi.nodes++;
                updateGlobal(pi.length, pi.nodes);
            }
        }
        for (int key : toRemove) maps[u].remove(key);

        // Add path for u itself
        PathInfo selfPath = new PathInfo(0, 1, u);
        if (!maps[u].containsKey(u_val) || maps[u].get(u_val).length < selfPath.length) {
            maps[u].put(u_val, selfPath);
            updateGlobal(0, 1);
        }

        // Merge light children
        for (int[] edge : adj[u]) {
            int v = edge[0];
            if (v != heavyChild) {
                for (Map.Entry<Integer, PathInfo> entry : maps[v].entrySet()) {
                    PathInfo pi = entry.getValue();
                    if (!(isAncestor(v, blockerNode) && isAncestor(blockerNode, pi.endNode))) {
                        long newLen = pi.length + edge[1];
                        int newNodes = pi.nodes + 1;
                        if (!maps[u].containsKey(entry.getKey()) || maps[u].get(entry.getKey()).length < newLen) {
                            maps[u].put(entry.getKey(), new PathInfo(newLen, newNodes, pi.endNode));
                        }
                        updateGlobal(newLen, newNodes);
                    }
                }
            }
        }

        valToNodeStack.get(nums[u]).pop();
    }

    private int getEdgeLength(int u, int v) {
        for (int[] edge : adj[u]) {
            if (edge[0] == v) return edge[1];
        }
        return 0; // Should not happen
    }
}
```
### Algorithm
*   **Preprocessing:**
    1.  Build an adjacency list for the tree.
    2.  Perform a single DFS from the root (0) to compute subtree sizes, parent pointers, and `tin`/`tout` times for each node. `tin[u]` and `tout[u]` are the entry and exit times of node `u` in the DFS traversal, which allow for O(1) ancestor checks (`is_ancestor(u, v)` is true if `tin[u] <= tin[v]` and `tout[u] >= tout[v]`).
*   **DSU on Trees (Sack) Framework:** We use a post-order traversal. The core idea is to compute results for smaller subtrees (light children) and merge them into the result of the largest subtree (heavy child) to avoid recomputing for the heavy path.
*   **State Representation:** For each node `u`, we compute a map, `M_u: end_val -> {length, nodes, end_node_id}`. This map stores information about the longest special paths that *start at `u`* and end at a descendant `d` (with `nums[d] = end_val`).
*   **Conflict Detection:** The main challenge is checking if a path can be extended. When at node `u`, to extend a path from a child `c`, we must ensure `nums[u]` is not present on the child's path. We use a global map of stacks, `valToNodeStack`, where `valToNodeStack[v]` stores a stack of nodes on the current DFS path from the root that have the value `v`. The top of the stack `valToNodeStack[nums[u]]` gives us the highest ancestor of the current node `u` that has the same value. This ancestor is a potential 'blocker'.
*   **Recursive DFS with Sack (`dfs_sack`):**
    1.  **Find Heavy Child:** For the current node `u`, identify its heavy child (the one with the largest subtree).
    2.  **Recurse on Light Children:** Call `dfs_sack` for all light children. After each call, clear the data computed for that light child to save memory.
    3.  **Recurse on Heavy Child:** Call `dfs_sack` for the heavy child, but instruct it to *keep* its computed map. This map becomes the base for `u`'s map.
    4.  **Merge Step:**
        a. **Update Heavy Child's Paths:** Iterate through the map inherited from the heavy child `hc`. For each path `hc -> ... -> d`, check if it's blocked by `nums[u]`. A path is blocked if the highest ancestor with value `nums[u]` (found using `valToNodeStack`) is a descendant of `hc`. If not blocked, update the path's length and node count by prepending the edge `u -> hc`.
        b. **Add Path for `u`:** Add the path consisting of only node `u` (length 0, 1 node) to the map.
        c. **Merge Light Children's Paths:** For each light child `lc`, re-run the DFS to get its map. Iterate through this map and merge valid, unblocked paths into `u`'s map.
    5.  **Update Global Answer:** After every modification to `u`'s map, update the global `maxLength` and `minNodes`.
    6.  **Manage State:** The `valToNodeStack` is updated in a preorder/postorder fashion within the main DFS traversal to correctly reflect the ancestor chain.