#3575

Maximum Good Subtree Score

candidate master · 1565 · lc hard +32 · 45.5% accepted · 51 likes · top 29%

Description

An undirected tree rooted at node 0 has n nodes (0-indexed). Each node i carries value vals[i] and has parent par[i].

A subset of nodes in a subtree is good when the decimal representations of all selected values together use each digit 0–9 at most once across all of them.

The score of a good subset is the sum of its node values.

Let maxScore[u] be the maximum score of any good subset within the subtree rooted at u (including u and all descendants).

Return the total sum of maxScore over all nodes, modulo 10⁹ + 7.

Code

1

2

3

class Solution:
    def goodSubtreeSum(self, vals: List[int], par: List[int]) -> int:

class Solution:
    def goodSubtreeSum(self, vals: List[int], par: List[int]) -> int: