3425. Longest Special Path Hard

1/**
2 * [3425] Longest Special Path
3 *
4 * 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.
5 * A <b data-stringify-type="bold">special path is defined as a <b data-stringify-type="bold">downward path from an ancestor node to a descendant node such that all the values of the nodes in that path are <b data-stringify-type="bold">unique.
6 * Note that a path may start and end at the same node.
7 * 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.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">edges = [[0,1,2],[1,2,3],[1,3,5],[1,4,4],[2,5,6]], nums = [2,1,2,1,3,1]</span>
12 * Output: <span class="example-io">[6,2]</span>
13 * Explanation:
14 * <h4>In the image below, nodes are colored by their corresponding values in nums</h4>
15 * <img alt="" src="https://assets.leetcode.com/uploads/2024/11/02/tree3.jpeg" style="width: 250px; height: 350px;" />
16 * 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.
17 * </div>
18 * <strong class="example">Example 2:
19 * <div class="example-block">
20 * Input: <span class="example-io">edges = [[1,0,8]], nums = [2,2]</span>
21 * Output: <span class="example-io">[0,1]</span>
22 * Explanation:
23 * <img alt="" src="https://assets.leetcode.com/uploads/2024/11/02/tree4.jpeg" style="width: 190px; height: 75px;" />
24 * 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.
25 * </div>
26 *  
27 * Constraints:
28 * 
29 * 	2 <= n <= 5 * 10^<span style="font-size: 10.8333px;">4</span>
30 * 	edges.length == n - 1
31 * 	edges[i].length == 3
32 * 	0 <= ui, vi < n
33 * 	1 <= lengthi <= 10^3
34 * 	nums.length == n
35 * 	0 <= nums[i] <= 5 * 10^4
36 * 	The input is generated such that edges represents a valid tree.
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/longest-special-path/
42// discuss: https://leetcode.com/problems/longest-special-path/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn longest_special_path(edges: Vec<Vec<i32>>, nums: Vec<i32>) -> Vec<i32> {
48        vec![]
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_3425() {
60    }
61}
62