# Longest Special Path II
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-special-path-ii)
Canonical: https://scaleengineer.com/dsa/problems/longest-special-path-ii
**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`. This is 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 in which all node values are **distinct**, except for **at most** one value that may appear twice.

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,1\],\[1,2,3\],\[1,3,1\],\[2,4,6\],\[4,7,2\],\[3,5,2\],\[3,6,5\],\[6,8,3\]\], nums = \[1,1,0,3,1,2,1,1,0\]

**Output:** \[9,3\]

**Explanation:**

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

![](https://assets.glich.co/dsa/longest-special-path-ii/image0.png)

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

**Example 2:**

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

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

**Explanation:**

![](https://assets.glich.co/dsa/longest-special-path-ii/image1.png)

The longest path is `0 -> 3` consisting of 2 nodes with a length of 5.

**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
## Simple Tree DP
A straightforward dynamic programming approach on the tree can be used. We can perform a post-order traversal (DFS) from the root. For each node, we compute information about the paths starting at that node and going downwards. This information is then passed up to its parent to compute information for longer paths.
**Time:** O(N^2) in the worst case. For each node, we iterate through its children's maps. In a path graph, this leads to a quadratic number of operations. · **Space:** O(N^2) in the worst case. For a path graph, the map returned by a node can contain entries for all nodes in its subtree.
**Pros:** Conceptually simpler than more optimized solutions.; Correct for all cases, just not efficient enough for large constraints.
**Cons:** The time complexity is high for certain tree structures like a line graph (or path graph), where the size of the map returned can grow up to O(N) at each level.; The space complexity is also high in the worst-case, as the maps can become large.
### Explanation
The core of this approach is a DFS function that, for each node `u`, calculates properties of paths starting at `u`. The function returns a map where keys are node values and values are pairs of `(length, nodes)`. `map[value]` stores the longest distinct-valued path starting at `u` that contains `value`.

When traversing, for a node `u`, we first recursively call the DFS on all its children. Each call for a child `v` returns a map `map_v`. We then merge `map_v` into `u`'s map, `map_u`. 

When merging, a path from `v` is extended to `u`. If `nums[u]` is the same as a value on the path from `v`, a special path with a repeated value is formed. We update our global answer. Otherwise, a new, longer distinct-valued path is formed. We update the global answer and merge this new path's information into `map_u`.

The main drawback is the merging process. In the worst case (e.g., a path graph), a node's map might need to incorporate a large map from its child, leading to `O(N^2)` complexity.

```java
class Solution {
    // Using a custom Pair class for {length, nodes}
    static class Pair {
        long len;
        int nodes;
        Pair(long len, int nodes) {
            this.len = len;
            this.nodes = nodes;
        }
    }

    long maxLength = -1;
    int minNodes = -1;

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

        List<List<int[]>> children = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            children.add(new ArrayList<>());
        }
        // Build a directed tree from the undirected graph
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        boolean[] visited = new boolean[n];
        visited[0] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                if (!visited[v]) {
                    visited[v] = true;
                    children.get(u).add(edge);
                    q.offer(v);
                }
            }
        }

        dfs(0, children, nums);
        return new int[]{(int)maxLength, minNodes};
    }

    private Map<Integer, Pair> dfs(int u, List<List<int[]>> children, int[] nums) {
        Map<Integer, Pair> mapU = new HashMap<>();
        mapU.put(nums[u], new Pair(0, 1));
        updateGlobal(0, 1);

        for (int[] edge : children.get(u)) {
            int v = edge[0];
            int length = edge[1];
            Map<Integer, Pair> mapV = dfs(v, children, nums);

            for (Map.Entry<Integer, Pair> entry : mapV.entrySet()) {
                int val = entry.getKey();
                Pair pathV = entry.getValue();
                long newLen = pathV.len + length;
                int newNodes = pathV.nodes + 1;

                if (val == nums[u]) { // Path with one repeat
                    updateGlobal(newLen, newNodes);
                } else { // Distinct path
                    updateGlobal(newLen, newNodes);
                    // Merge into mapU
                    if (!mapU.containsKey(val) || isBetter(newLen, newNodes, mapU.get(val))) {
                        mapU.put(val, new Pair(newLen, newNodes));
                    }
                }
            }
        }
        return mapU;
    }

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

    private boolean isBetter(long len1, int nodes1, Pair p2) {
        if (len1 > p2.len) return true;
        if (len1 == p2.len && nodes1 < p2.nodes) return true;
        return false;
    }
}
```
### Algorithm
1.  Represent the tree using an adjacency list where each entry stores the neighbor and the edge length.
2.  Define a recursive DFS function, say `dfs(u, p)`, that traverses the tree in a post-order fashion. This function will compute and return information about paths starting at node `u` and descending into its subtree.
3.  The information returned by `dfs(u, p)` will be a map, let's call it `pathMap`. The keys of this map are node values, and the values are pairs `(length, nodes)` representing a path. Specifically, `pathMap[val]` will store the `(length, nodes)` of the longest downward path with distinct node values starting at `u` that contains the value `val`.
4.  Inside `dfs(u, p)`:
    a. Initialize a map for the current node `u`, `map_u`. Add the path consisting of only `u` itself: `map_u.put(nums[u], (0L, 1))`. Update the global answer with this path.
    b. For each child `v` of `u`, recursively call `dfs(v, u)` to get its map, `map_v`.
    c. Merge `map_v` into `map_u`. For each entry `(val, path)` in `map_v`:
        i. Create a new path by prepending `u`. The new path has length `path.length + edge_length(u, v)` and `path.nodes + 1` nodes.
        ii. If `val == nums[u]`, this new path has a repeated value (`nums[u]`). This is a valid special path. Update the global answer with this new path's properties.
        iii. If `val != nums[u]`, the new path is still a distinct-valued path. Update the global answer. Then, merge this new path's information into `map_u`. For every value `x` on this new path (which are `nums[u]` and the values from the path from `v`), we should update `map_u[x]`. Since we don't store all values on the path, we can only update `map_u[val]` and `map_u[nums[u]]` with the new path, taking the maximum if an entry already exists.
5.  The global answer, a pair `(maxLength, minNodes)`, is updated whenever a valid special path (either distinct-valued or with one repeat) is found or created. The update logic is: if the new path is longer, replace the answer. If it's equally long, take the one with fewer nodes.

## Tree DP with Sack (DSU on Trees) Optimization
This approach optimizes the simple Tree DP by using a technique known as Sack, or DSU on trees. The main bottleneck in the previous approach was the repeated construction and merging of path information maps. Sack optimization reduces this redundant work by applying a heavy-light decomposition strategy to the tree traversal.
**Time:** O(N log N). Each node's information is part of a map that is created and merged at most O(log N) times up the tree. Each merge operation takes time proportional to the size of the smaller map. · **Space:** O(N). The total size of all maps at any point in the recursion is bounded by O(N).
**Pros:** Highly efficient, with a time complexity that can pass the given constraints.; It's a general and powerful technique for a class of tree problems where information needs to be aggregated from subtrees.
**Cons:** Significantly more complex to implement correctly compared to the simple DP.; The logic for merging and updating maps requires careful handling of multiple cases.
### Explanation
The algorithm is a sophisticated form of tree DP. We first determine the size of each node's subtree. This allows us to distinguish between a node's 'heavy' child (the one with the largest subtree) and its 'light' children.

The main DFS traversal processes nodes in a specific order to minimize work. For a node `u`, it first recursively visits all light children, computes the answer for their subtrees, and then discards their path information. Then, it visits the heavy child and *reuses* its computed path map. This map is updated to reflect paths starting from `u` through the heavy child.

Finally, it revisits the light children's subtrees, computes their path maps again, and merges this information into the main map inherited from the heavy child. During all these steps, we check for the two types of special paths:
1.  **Distinct-valued paths**: Any path in our map is a distinct-valued path. We update the global answer whenever we create or lengthen one.
2.  **One-repeat paths**: These are formed when we extend a path from a child `v` with its parent `u`, and `nums[u]` is already present on the path from `v`. We detect this when the value `nums[u]` is a key in the child's path map.

The Sack technique ensures that information from smaller subtrees is merged into information from larger ones, limiting the total number of map operations across the entire traversal to `O(N log N)`. 

```java
class Solution {
    static class Pair {
        long len;
        int nodes;
        Pair(long len, int nodes) {
            this.len = len;
            this.nodes = nodes;
        }
    }

    long maxLength = -1;
    int minNodes = -1;
    List<List<int[]>> children;
    int[] subtreeSize;
    int[] nums;

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

        children = new ArrayList<>();
        for (int i = 0; i < n; i++) children.add(new ArrayList<>());
        subtreeSize = new int[n];
        buildTreeAndSizes(0, -1, adj);

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

    private void buildTreeAndSizes(int u, int p, List<List<int[]>> adj) {
        subtreeSize[u] = 1;
        for (int[] edge : adj.get(u)) {
            int v = edge[0];
            if (v == p) continue;
            children.get(u).add(edge);
            buildTreeAndSizes(v, u, adj);
            subtreeSize[u] += subtreeSize[v];
        }
    }

    private Map<Integer, Pair> dfsSack(int u) {
        int heavyChild = -1, maxSubtree = -1, heavyChildLen = 0;
        for (int[] edge : children.get(u)) {
            int v = edge[0];
            if (subtreeSize[v] > maxSubtree) {
                maxSubtree = subtreeSize[v];
                heavyChild = v;
                heavyChildLen = edge[1];
            }
        }

        Map<Integer, Pair> mapU = new HashMap<>();
        for (int[] edge : children.get(u)) {
            int v = edge[0];
            if (v != heavyChild) {
                dfsSack(v); // Discard result, global answer is updated
            }
        }

        if (heavyChild != -1) {
            mapU = dfsSack(heavyChild);
            Map<Integer, Pair> newMapU = new HashMap<>();
            for (Map.Entry<Integer, Pair> entry : mapU.entrySet()) {
                int val = entry.getKey();
                Pair path = entry.getValue();
                long newLen = path.len + heavyChildLen;
                int newNodes = path.nodes + 1;
                if (val == nums[u]) {
                    updateGlobal(newLen, newNodes);
                } else {
                    newMapU.put(val, new Pair(newLen, newNodes));
                }
            }
            mapU = newMapU;
        }

        for (int[] edge : children.get(u)) {
            int v = edge[0];
            int length = edge[1];
            if (v != heavyChild) {
                Map<Integer, Pair> mapV = dfsSack(v);
                for (Map.Entry<Integer, Pair> entry : mapV.entrySet()) {
                    int val = entry.getKey();
                    Pair pathV = entry.getValue();
                    long newLen = pathV.len + length;
                    int newNodes = pathV.nodes + 1;
                    if (val == nums[u]) {
                        updateGlobal(newLen, newNodes);
                    } else {
                        if (!mapU.containsKey(val) || isBetter(newLen, newNodes, mapU.get(val))) {
                            mapU.put(val, new Pair(newLen, newNodes));
                        }
                    }
                }
            }
        }

        if (!mapU.containsKey(nums[u]) || isBetter(0, 1, mapU.get(nums[u]))) {
             mapU.put(nums[u], new Pair(0, 1));
        }
        
        for(Pair p : mapU.values()){
            updateGlobal(p.len, p.nodes);
        }

        return mapU;
    }

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

    private boolean isBetter(long len1, int nodes1, Pair p2) {
        if (len1 > p2.len) return true;
        if (len1 == p2.len && nodes1 < p2.nodes) return true;
        return false;
    }
}
```
### Algorithm
1.  **Preprocessing**: Perform a preliminary DFS from the root (node 0) to build a directed child-only adjacency list and to compute the subtree size for each node.
2.  **Heavy-Light Decomposition Idea**: In the main DFS traversal, for each node `u`, identify its "heavy child" - the child with the largest subtree. All other children are "light children".
3.  **Main DFS (`dfs_sack`)**: This function will solve the problem for the subtree at `u` and return a map representing paths, similar to the simple DP approach.
    a. Recursively call `dfs_sack` for all light children of `u`. After each call returns, we clear the map data generated for that light subtree. The global answer will have been updated for paths entirely within that light subtree.
    b. Recursively call `dfs_sack` for the heavy child `hc`. Crucially, we *keep* the map returned from this call.
    c. This inherited map from `hc` contains paths starting at `hc`. We transform it into a map for paths starting at `u` (by adding the edge `(u, hc)` length and incrementing node counts).
    d. While transforming, if we encounter a path that now creates a repeat with `nums[u]`, we've found a special path. We update the global answer. These entries are then conceptually removed from being 'distinct' paths.
    e. Add the path of node `u` itself (`(0, 1)`) to the map and update the global answer.
    f. Now, merge the light children's information. For each light child `lc`, we do another DFS on its subtree to collect its path map. Then, we iterate through this temporary map and merge its information into the main map (from the heavy child), updating the global answer for any new special paths (repeated or distinct) that are formed.
4.  **Sack Optimization**: The key is that we only do a full traversal and map creation for light subtrees. The map from the heavy child is reused. Since a path from the root to any node crosses at most `O(log N)` light edges, each node's information is merged at most `O(log N)` times. This reduces the overall complexity.