3772. Maximum Subgraph Score in a Tree Hard

1/**
2 * [3772] Maximum Subgraph Score in a Tree
3 *
4 * You are given an undirected tree with n nodes, numbered from 0 to n - 1. It is represented by a 2D integer array edges​​​​​​​ of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
5 * You are also given an integer array good of length n, where good[i] is 1 if the i^th node is good, and 0 if it is bad.
6 * Define the score of a subgraph as the number of good nodes minus the number of bad nodes in that subgraph.
7 * For each node i, find the maximum possible score among all connected subgraphs that contain node i.
8 * Return an array of n integers where the i^th element is the maximum score for node i.
9 * A subgraph is a graph whose vertices and edges are subsets of the original graph.
10 * A connected subgraph is a subgraph in which every pair of its vertices is reachable from one another using only its edges.
11 *  
12 * <strong class="example">Example 1:
13 * <img alt="Tree Example 1" src="https://assets.leetcode.com/uploads/2025/11/17/tree1fixed.png" style="width: 271px; height: 51px;" />
14 * <div class="example-block">
15 * Input: <span class="example-io">n = 3, edges = [[0,1],[1,2]], good = [1,0,1]</span>
16 * Output: <span class="example-io">[1,1,1]</span>
17 * Explanation:
18 * 
19 * 	Green nodes are good and red nodes are bad.
20 * 	For each node, the best connected subgraph containing it is the whole tree, which has 2 good nodes and 1 bad node, resulting in a score of 1.
21 * 	Other connected subgraphs containing a node may have the same score.
22 * </div>
23 * <strong class="example">Example 2:
24 * <img alt="Tree Example 2" src="https://assets.leetcode.com/uploads/2025/11/17/tree2.png" style="width: 211px; height: 231px;" />
25 * <div class="example-block">
26 * Input: <span class="example-io">n = 5, edges = [[1,0],[1,2],[1,3],[3,4]], good = [0,1,0,1,1]</span>
27 * Output: <span class="example-io">[2,3,2,3,3]</span>
28 * Explanation:
29 * 
30 * 	Node 0: The best connected subgraph consists of nodes 0, 1, 3, 4, which has 3 good nodes and 1 bad node, resulting in a score of 3 - 1 = 2.
31 * 	Nodes 1, 3, and 4: The best connected subgraph consists of nodes 1, 3, 4, which has 3 good nodes, resulting in a score of 3.
32 * 	Node 2: The best connected subgraph consists of nodes 1, 2, 3, 4, which has 3 good nodes and 1 bad node, resulting in a score of 3 - 1 = 2.
33 * </div>
34 * <strong class="example">Example 3:
35 * <img alt="Tree Example 3" src="https://assets.leetcode.com/uploads/2025/11/17/tree3.png" style="width: 161px; height: 51px;" />
36 * <div class="example-block">
37 * Input: <span class="example-io">n = 2, edges = [[0,1]], good = [0,0]</span>
38 * Output: <span class="example-io">[-1,-1]</span>
39 * Explanation:
40 * For each node, including the other node only adds another bad node, so the best score for both nodes is -1.
41 * </div>
42 *  
43 * Constraints:
44 * 
45 * 	2 <= n <= 10^5
46 * 	edges.length == n - 1
47 * 	edges[i] = [ai, bi]
48 * 	0 <= ai, bi < n
49 * 	good.length == n
50 * 	0 <= good[i] <= 1
51 * 	The input is generated such that edges represents a valid tree.
52 * 
53 */
54pub struct Solution {}
55
56// problem: https://leetcode.com/problems/maximum-subgraph-score-in-a-tree/
57// discuss: https://leetcode.com/problems/maximum-subgraph-score-in-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
58
59// submission codes start here
60
61impl Solution {
62    pub fn max_subgraph_score(n: i32, edges: Vec<Vec<i32>>, good: Vec<i32>) -> Vec<i32> {
63        vec![]
64    }
65}
66
67// submission codes end
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn test_3772() {
75    }
76}
77