Find the Best Connected Strength for Every Tree Node

Problem Statement

You are given an undirected tree with n nodes labeled from 0 to n - 1. Each node represents a neuron and has a strength value given in an array weights of length n, where weights[i] is either 1 (strong) or -1 (weak).

A connected component in the tree is considered valid for node u if it is a non-empty connected subgraph of the tree that contains node u. The total strength of such a component is the sum of weights[v] for all nodes v in the component.

Return an array ans of length n, where ans[i] is the maximum possible total strength of a valid connected component containing node i.

Function Signature

def maxConnectedStrength(n: int, edges: list[list[int]], weights: list[int]) -> list[int]:
    pass

Input Format

• n: An integer representing the number of nodes.
• edges: A 2D integer array of size (n - 1) x 2 where edges[i] = [u, v] represents an undirected edge between nodes u and v.
• weights: A list of integers of length n, where each weights[i] ∈ {-1, 1}.

Output Format

• Returns a list of n integers where the i-th value is the maximum connected strength for node i.

Constraints

• 1 <= n <= 10^5
• edges.length == n - 1
• 0 <= edges[i][0], edges[i][1] < n
• The input graph is guaranteed to be a connected, undirected tree.
• weights[i] is either 1 or -1.

Examples

Example 1

Input:
n = 5
edges = [[0, 1], [0, 2], [1, 3], [1, 4]]
weights = [1, -1, 1, 1, 1]

Output:
[3, 2, 3, 2, 2]

Explanation:
- For node 0: The component {0, 2, 1, 3, 4} has strength 1 + 1 + (-1) + 1 + 1 = 3.
- For node 1: Even though weights[1] = -1, connecting to {3, 4} gives -1 + 1 + 1 = 1, and connecting to {0, 2} adds +2, giving total 2.
- For node 2: Connecting to {0, 1, 3, 4} gives 1 + (1 - 1 + 1 + 1) = 3.
- For node 3: Connecting through 1 to {0, 2, 4} gives 1 + (-1 + 1 + 1 + 1) = 3... wait, if node 3 includes node 1, the optimal subset is {3, 1, 4, 0, 2} which gives sum 1 - 1 + 1 + 1 + 1 = 3. Wait, if node 3 takes just {3, 1, 4}, sum is 1 - 1 + 1 = 1; with {0, 2}, sum is 3. For node 3, the maximum is indeed 3 (or 2 if isolated). Here all nodes can reach the positive sum.

Example 2

Input:
n = 3
edges = [[0, 1], [1, 2]]
weights = [-1, -1, -1]

Output:
[-1, -1, -1]

Explanation:
Every node has weight -1. Any larger connected set would only add more -1s, so each node achieves its maximum by taking only itself (strength -1).

Edge Cases

• n = 1: The only component is the node itself; answer is [weights[0]].
• All nodes have weight -1: Every node's optimal component consists solely of itself, returning [-1, -1, ...].
• All nodes have weight 1: Every node can include the entire tree, returning [n, n, ...].