← 返回 akunacapital 的题目列表Star Sum of Graph
类型：online_judge
Given an undirected graph with nodes numbered from 1 to n, where each node has a weight. Define the Star Sum of a node v as the total sum of weights of a star structure centered at v (including v itself and all its neighboring nodes). You need to find the maximum Star Sum among all nodes in the graph.
Input:
The first line contains an integer n, the number of nodes.
The second line contains n integers, representing the weights of each node.
The following m lines each contain two integers u and v, indicating an undirected edge between nodes u and v.
Output:
An integer representing the maximum Star Sum among all nodes.
Sample Input
4
1 2 3 4
1 2
2 3
3 4
Sample Output
9
Constraints:
1 <= n <= 1000
Weights are non-negative integers
No duplicate edges or cycles.
Example
Input
4
1 2 3 4
1 2
2 3
3 4