← 返回 microsoft 的题目列表Maximum Strength of Each Neuron in a Tree Network
类型：online_judge
Problem: Maximum Strength of Each Neuron in a Tree Network
You are given a tree-shaped network with n neurons numbered from 1 to n. The network has n - 1 undirected edges.
Each neuron has a property strongConnectivity[i]:
strongConnectivity[i] = 1 means neuron i + 1 is strongly connected;
strongConnectivity[i] = 0 means neuron i + 1 is weakly connected.
The score of a connected subnetwork is defined as:
number of strongly connected neurons - number of weakly connected neurons
For each neuron u, its strength is the maximum score among all connected subnetworks that contain u.
Return an array neuronStrengths of length n, where neuronStrengths[i] is the strength of neuron i + 1.
Input Format
The first line contains an integer n.
The second line contains n integers, the array strongConnectivity.
The next n - 1 lines each contain two integers u v, representing an undirected edge.
Output Format
Print n integers, the maximum strength for every node.
Constraints
1 <= n <= 2 * 10^5
strongConnectivity[i] in {0, 1}
1 <= u, v <= n
The given edges form a tree.
Example
Input:
4
0 0 1 0
1 2
1 3
1 4
Output:
0 -1 1 -1
Explanation:
Node 1 can choose the connected subnetwork containing nodes 1 and 3, whose score is 1 - 1 = 0.
Node 3 is strongly connected, so choosing only node 3 gives score 1.
Example
Input
4
0 0 1 0
1 2
1 3
1 4
Output
0 -1 1 -1