Maximum Importance of Roads

Given n cities and undirected roads, assign importance values to cities so that the total importance of all roads is maximized. Pattern focus: Graph Degree Analysis. High-degree nodes should receive larger labels to maximize the sum over road endpoints.

Input Format

n = number of cities, roads = undirected edges

Output Format

maximum total importance of all roads

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • n, roads must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

n = 5
roads = [[0,1],[1,2],[2,3],[2,4]]

Output:

29

Explanation:

Assign larger values to higher-degree cities.

Example 2:

Input:

n = 2
roads = [[0,1]]

Output:

3

Explanation:

With two cities, the best assignment is 1 and 2.

Loading...
Maximum Importance of Roads - Graph Fundamentals