#3772

Maximum Subgraph Score in a Tree

expert · 1000 · lc hard +32 · 70.5% accepted · 49 likes · top 79%

Description

Given an undirected tree of n nodes (0-indexed) with edges edges[i] = [ai, bi] and a binary array good where good[i] = 1 marks a good node and good[i] = 0 marks a bad node, define a subgraph's score as (good nodes) minus (bad nodes), and for each node i return the maximum score over all connected subgraphs that include node i.

Code

1

2

3

class Solution:
    def maxSubgraphScore(self, n: int, edges: List[List[int]], good: List[int]) -> List[int]:

class Solution:
    def maxSubgraphScore(self, n: int, edges: List[List[int]], good: List[int]) -> List[int]: