Longest Special Path
hard · 22.5% accepted · 126 likes · top 3%
array · hash table · tree · depth-first search · prefix sum
Description
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.
Solution