Maximum Good Subtree Score
hard · 45.5% accepted · 51 likes · top 29%
array · dynamic programming · bit manipulation · tree · depth-first search · bitmask
Description
You are given an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. Each node i has an integer value vals[i], and its parent is given by par[i].
A subset of nodes within the subtree of a node is called good if every digit from 0 to 9 appears at most once in the decimal representation of the values of the selected nodes.
The score of a good subset is the sum of the values of its nodes.
Define an array maxScore of length n, where maxScore[u] represents the maximum possible sum of values of a good subset of nodes that belong to the subtree rooted at node u, including u itself and all its descendants.
Return the sum of all values in maxScore.
Since the answer may be large, return it modulo 109 + 7.
Solution