Tap here to switch tabs
Problem
Submissions

Problem: Maximum Subgraph Score in a Tree

Try to solve the Maximum Subgraph Score in a Tree problem.

Statement

You are given an integer n representing the number of nodes in an undirected tree, with nodes numbered from 00 to n −1- 1. You are also given a 22D integer array edges where edges[i] =[ai,bi]= [a_i, b_i] denotes an undirected edge between nodes aia_i and bib_i, and a binary array good of size n where good[i] =1= 1 means node i is good, and good[i] =0= 0 means node i is bad.

The score of a connected subgraph is calculated as the count of good nodes minus the count of bad nodes contained within that subgraph.

Return an array ans of size n where ans[i] is the maximum score among all connected subgraphs containing node i.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • edges.length == n −1- 1

  • edges[i] =[ai,bi]= [a_i, b_i]

  • 0≤ai,bi<0 \leq a_i, b_i < n

  • good.length == n

  • 0≤0 \leq good[i] ≤1\leq 1

  • The input is generated such that edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Subgraph Score in a Tree

Try to solve the Maximum Subgraph Score in a Tree problem.

Statement

You are given an integer n representing the number of nodes in an undirected tree, with nodes numbered from 00 to n −1- 1. You are also given a 22D integer array edges where edges[i] =[ai,bi]= [a_i, b_i] denotes an undirected edge between nodes aia_i and bib_i, and a binary array good of size n where good[i] =1= 1 means node i is good, and good[i] =0= 0 means node i is bad.

The score of a connected subgraph is calculated as the count of good nodes minus the count of bad nodes contained within that subgraph.

Return an array ans of size n where ans[i] is the maximum score among all connected subgraphs containing node i.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • edges.length == n −1- 1

  • edges[i] =[ai,bi]= [a_i, b_i]

  • 0≤ai,bi<0 \leq a_i, b_i < n

  • good.length == n

  • 0≤0 \leq good[i] ≤1\leq 1

  • The input is generated such that edges represents a valid tree.