Problem

You are given an undirected connected graph of n nodes, numbered from 0 to n - 1. Each node is connected to at most 2 other nodes.

The graph consists of m edges, represented by a 2D array edges, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi.

You have to assign a unique value from 1 to n to each node. The value of an edge will be the product of the values assigned to the two nodes it connects.

Your score is the sum of the values of all edges in the graph.

Return the maximum score you can achieve.

Example 1

1
2
3
4
5
6
7
![](https://assets.leetcode.com/uploads/2025/05/12/screenshot-
from-2025-05-13-01-27-52.png)
Input: n = 4, edges = [[0,1],[1,2],[2,3]]
Output: 23
Explanation:
The diagram above illustrates an optimal assignment of values to nodes. The
sum of the values of the edges is: `(1 * 3) + (3 * 4) + (4 * 2) = 23`.

Example 2

1
2
3
4
5
6
7
![](https://assets.leetcode.com/uploads/2025/03/23/graphproblemex2drawio.png)
Input: n = 6, edges = [[0,3],[4,5],[2,0],[1,3],[2,4],[1,5]]
Output: 82
Explanation:
The diagram above illustrates an optimal assignment of values to nodes. The
sum of the values of the edges is: `(1 * 2) + (2 * 4) + (4 * 6) + (6 * 5) + (5
* 3) + (3 * 1) = 82`.

Constraints

  • 1 <= n <= 5 * 10^4
  • m == edges.length
  • 1 <= m <= n
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • There are no repeated edges.
  • The graph is connected.
  • Each node is connected to at most 2 other nodes.

Examples

Solution

Method 1 – Greedy Degree Assignment

Intuition

The key idea is that nodes with higher degrees (connected to more edges) should be assigned higher values to maximize the sum of edge products. Since each node is connected to at most 2 other nodes, we can sort nodes by their degree and assign the largest values to the most connected nodes.

Approach

  1. Count the degree (number of edges) for each node.
  2. Sort nodes by degree in descending order.
  3. Assign values from n down to 1 to nodes in order of their degree.
  4. Calculate the sum of products for each edge using the assigned values.

Complexity

  • ⏰ Time complexity: O(n + m + n log n) — Counting degrees is O(m), sorting is O(n log n), assignment and sum calculation are O(m).
  • 🧺 Space complexity: O(n + m) — For degree array, value mapping, and edge list.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maximumSumOfEdgeValues(int n, vector<vector<int>>& edges) {
        vector<int> deg(n);
        for (auto& e : edges) {
            deg[e[0]]++;
            deg[e[1]]++;
        }
        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b) { return deg[a] > deg[b]; });
        vector<int> val(n);
        for (int i = 0; i < n; ++i) val[idx[i]] = n - i;
        int ans = 0;
        for (auto& e : edges) ans += val[e[0]] * val[e[1]];
        return ans;
    }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func maximumSumOfEdgeValues(n int, edges [][]int) int {
    deg := make([]int, n)
    for _, e := range edges {
        deg[e[0]]++
        deg[e[1]]++
    }
    idx := make([]int, n)
    for i := range idx { idx[i] = i }
    sort.Slice(idx, func(i, j int) bool { return deg[idx[i]] > deg[idx[j]] })
    val := make([]int, n)
    for i, v := range idx { val[v] = n - i }
    ans := 0
    for _, e := range edges { ans += val[e[0]] * val[e[1]] }
    return ans
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int maximumSumOfEdgeValues(int n, int[][] edges) {
        int[] deg = new int[n];
        for (int[] e : edges) {
            deg[e[0]]++;
            deg[e[1]]++;
        }
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; ++i) idx[i] = i;
        Arrays.sort(idx, (a, b) -> deg[b] - deg[a]);
        int[] val = new int[n];
        for (int i = 0; i < n; ++i) val[idx[i]] = n - i;
        int ans = 0;
        for (int[] e : edges) ans += val[e[0]] * val[e[1]];
        return ans;
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    fun maximumSumOfEdgeValues(n: Int, edges: Array<IntArray>): Int {
        val deg = IntArray(n)
        for (e in edges) {
            deg[e[0]]++
            deg[e[1]]++
        }
        val idx = (0 until n).toList().sortedByDescending { deg[it] }
        val valArr = IntArray(n)
        for (i in idx.indices) valArr[idx[i]] = n - i
        var ans = 0
        for (e in edges) ans += valArr[e[0]] * valArr[e[1]]
        return ans
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def maximum_sum_of_edge_values(n: int, edges: list[list[int]]) -> int:
    deg = [0] * n
    for a, b in edges:
        deg[a] += 1
        deg[b] += 1
    idx = sorted(range(n), key=lambda x: -deg[x])
    val = [0] * n
    for i, v in enumerate(idx):
        val[v] = n - i
    ans = 0
    for a, b in edges:
        ans += val[a] * val[b]
    return ans
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn maximum_sum_of_edge_values(n: i32, edges: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut deg = vec![0; n];
        for e in &edges {
            deg[e[0] as usize] += 1;
            deg[e[1] as usize] += 1;
        }
        let mut idx: Vec<_> = (0..n).collect();
        idx.sort_by_key(|&x| -deg[x]);
        let mut val = vec![0; n];
        for (i, &v) in idx.iter().enumerate() {
            val[v] = n - i;
        }
        let mut ans = 0;
        for e in &edges {
            ans += val[e[0] as usize] * val[e[1] as usize];
        }
        ans as i32
    }
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    maximumSumOfEdgeValues(n: number, edges: number[][]): number {
        const deg = Array(n).fill(0);
        for (const [a, b] of edges) {
            deg[a]++;
            deg[b]++;
        }
        const idx = Array.from({length: n}, (_, i) => i).sort((a, b) => deg[b] - deg[a]);
        const val = Array(n).fill(0);
        for (let i = 0; i < n; ++i val[idx[i]] = n - i;
        let ans = 0;
        for (const [a, b] of edges) ans += val[a] * val[b];
        return ans;
    }
}