3486. Longest Special Path II Hard

1/**
2 * [3486] Longest Special Path II
3 *
4 * 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.
5 * 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.
6 * Return an array <code data-stringify-type="code">result of size 2, where result[0] is the <b data-stringify-type="bold">length of the longest special path, and result[1] is the <b data-stringify-type="bold">minimum number of nodes in all <i data-stringify-type="italic">possible longest special paths.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">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]</span>
11 * Output: <span class="example-io">[9,3]</span>
12 * Explanation:
13 * In the image below, nodes are colored by their corresponding values in nums.
14 * <img alt="" src="https://assets.leetcode.com/uploads/2025/02/18/e1.png" style="width: 190px; height: 270px;" />
15 * 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.
16 * </div>
17 * <strong class="example">Example 2:
18 * <div class="example-block">
19 * Input: <span class="example-io">edges = [[1,0,3],[0,2,4],[0,3,5]], nums = [1,1,0,2]</span>
20 * Output: <span class="example-io">[5,2]</span>
21 * Explanation:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2025/02/18/e2.png" style="width: 150px; height: 110px;" />
23 * The longest path is 0 -> 3 consisting of 2 nodes with a length of 5.
24 * </div>
25 *  
26 * Constraints:
27 * 
28 * 	2 <= n <= 5 * 10^<span style="font-size: 10.8333px;">4</span>
29 * 	edges.length == n - 1
30 * 	edges[i].length == 3
31 * 	0 <= ui, vi < n
32 * 	1 <= lengthi <= 10^3
33 * 	nums.length == n
34 * 	0 <= nums[i] <= 5 * 10^4
35 * 	The input is generated such that edges represents a valid tree.
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/longest-special-path-ii/
41// discuss: https://leetcode.com/problems/longest-special-path-ii/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn longest_special_path(edges: Vec<Vec<i32>>, nums: Vec<i32>) -> Vec<i32> {
47        vec![]
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_3486() {
59    }
60}
61