3547. Maximum Sum of Edge Values in a Graph Hard

1/**
2 * [3547] Maximum Sum of Edge Values in a Graph
3 *
4 * 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.
5 * 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.
6 * <p data-end="502" data-start="345">You have to assign a unique value from <code data-end="391" data-start="388">1 to <code data-end="398" data-start="395">n to each node. The value of an edge will be the product of the values assigned to the two nodes it connects.
7 * <p data-end="502" data-start="345">Your score is the sum of the values of all edges in the graph.
8 * Return the maximum score you can achieve.
9 *  
10 * <strong class="example">Example 1:
11 * <img alt="" src="https://assets.leetcode.com/uploads/2025/05/12/screenshot-from-2025-05-13-01-27-52.png" style="width: 411px; height: 123px;" />
12 * <div class="example-block">
13 * Input: <span class="example-io">n = 4, edges = </span>[[0,1],[1,2],[2,3]]
14 * Output: 23
15 * Explanation:
16 * 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.
17 * </div>
18 * <strong class="example">Example 2:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2025/03/23/graphproblemex2drawio.png" style="width: 220px; height: 255px;" />
20 * <div class="example-block">
21 * Input: <span class="example-io">n = 6, edges = [[0,3],[4,5],[2,0],[1,3],[2,4],[1,5]]</span>
22 * Output: <span class="example-io">82</span>
23 * Explanation:
24 * 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.
25 * </div>
26 *  
27 * Constraints:
28 * 
29 * 	1 <= n <= 5 * 10^4
30 * 	m == edges.length
31 * 	1 <= m <= n
32 * 	edges[i].length == 2
33 * 	0 <= ai, bi < n
34 * 	ai != bi
35 * 	There are no repeated edges.
36 * 	The graph is connected.
37 * 	Each node is connected to at most 2 other nodes.
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/maximum-sum-of-edge-values-in-a-graph/
43// discuss: https://leetcode.com/problems/maximum-sum-of-edge-values-in-a-graph/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn max_score(n: i32, edges: Vec<Vec<i32>>) -> i64 {
49        
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_3547() {
61    }
62}
63