#3547
Hard Algorithms Maximum sum of edge values in a graph
Math Greedy Graph Theory
35.7% acceptance
Feb 25, 2026
50
30
Given an undirected connected graph where each node has at most 2 neighbors (paths and cycles).
Assign unique values 1..n to nodes. Score = sum of (product of values at endpoints) for each edge.
Return the maximum score.
Solution
Rust
Time O(n * m)
Space O(n * m)
impl Solution {
pub fn max_score(n: i32, edges: Vec<Vec<i32>>) -> i64 {
let n = n as usize;
let mut adj = vec![vec![]; n];
for e in &edges {
adj[e[0] as usize].push(e[1] as usize);
adj[e[1] as usize].push(e[0] as usize);
}
// Each node has degree 1 or 2 -> graph is a single path or a single cycle
// (given it's connected with m=n or m=n-1)
let m = edges.len();
// Values to assign: 1..n (highest = n, n-1, ..., 1)
// For a path of length n: optimal assignment puts large values at "interior" positions
// where each interior node contributes to 2 edges.
// For cycle: all nodes are interior (degree 2).
if m == n {
// Cycle: all nodes have degree 2
// In a cycle of length n with values a1,a2,...,an:
// score = a1*a2 + a2*a3 + ... + a(n-1)*an + an*a1
// = sum over edges of products
// To maximize: interleave largest with second largest etc.
// For even n: pair n with n-1, n-2 with n-3, etc. -> score = sum(i * (i-1)) for odd i = n,n-2,...
// For odd n: similar but one element paired with next two
// Actually the closed form: for a cycle, best to put alternating large-small.
// Put values n, n-1, n-2, ..., 1 on the cycle in order and compute:
// Optimal for cycle: place n, (n-2), (n-4),..., then (n-1), (n-3)...
// Score for cycle = n*(n-1) + (n-2)*(n-3) + ... (adjacent pairs)
// This is the same as for path (the last edge reconnects)
let vals: Vec<i64> = (1..=n as i64).rev().collect();
// Best arrangement for cycle: interleave big and small
// Sum formula: pair consecutive in sorted descending: (n)(n-1) + (n-2)(n-3) + ...
// For cycle with n values, score = same as pairing them optimally
// Known result: for cycle, optimal = same as path optimal + ...
// Let's compute: sort descending, pair (0,1),(2,3),...
// For even n: score = n*(n-1) + (n-2)*(n-3) + ...
// For odd n: n*(n-1) + (n-2)*(n-3) + ... + 2*1 -- wait that's only n/2 pairs for n-1 edges
// A cycle has n edges. We need n products summed.
// Actually for a cycle v1-v2-...-vn-v1, if we assign sorted values:
// best = place them in "alternating" pattern. But analysis shows:
// score = n * (n-1) + (n-2)*(n-3) + ...? No that's only n/2 terms.
//
// For the cycle, we think of it as: each node i is multiplied by its two neighbors.
// The sum = sum_i val[i] * (val[left_i] + val[right_i])
// = sum_edges val[u]*val[v]
// To maximize: put large values next to each other? No, it's better to put large
// values next to other large values because they multiply.
// Actually putting them all adjacent: n*(n-1) edge gives n*(n-1) contribution.
// Greedy: sort descending, place adjacently in cycle.
// For cycle with values n,n-1,n-2,...,1 in order:
// score = n*(n-1) + (n-1)*(n-2) + ... + 2*1 + 1*n
// Let's just compute using pairs: take values sorted descending, form pairs
// For cycle, we can split into a path; best path assignment + reconnect.
// Known optimal: for cycle n nodes -> score = (n)*(n-1) + (n-2)*(n-3) + ...
// This is achieved by alternating high-low.
// But this gives only floor(n/2) edges' contribution? No, we need all n edges.
// Correct approach: In the cycle, place values such that the n largest values
// are in positions that maximize edge products.
// Optimal ordering for a cycle: place values in pattern big, small, big, small...
// When n is even: 2,4,6,...,n,1,3,5,...,n-1 gives sum that can be computed.
// Simpler proven result: for n nodes in a cycle or path, the maximum score is achieved
// by pairing up adjacent values: (n)(n-1) + (n-2)(n-3) + ...
// A cycle of n has n edges. With n values assigned, the maximum sum of adjacent products
// = n*(n-1) + (n-2)*(n-3) + ... which has floor(n/2) terms... not n terms.
//
// I'll just simulate: the cycle score depends on the layout.
// For cycle of n: best score = sum_{i=1}^{n} val[i]*val[i+1 mod n]
// Proven: optimal is consecutive in sorted order: n*(n-1)+(n-1)*(n-2)+...+2*1+1*n
// But that's not right either. Let me just use the greedy known result.
//
// KNOWN: for a path of n nodes, max score = n*(n-1) + (n-2)*(n-3) + ... (pair from top)
// For a cycle of n nodes, max score = same as path of n+1 minus smallest element? No.
//
// Actually, let me think: for cycle with n even:
// Place n at pos 1, then n-2, n-4, ..., 2 going clockwise
// and n-1, n-3, ..., 1 going counterclockwise
// This gives edges: n*(n-1), n*(n-2+1)... complex.
//
// I'll just use the formula: max_cycle = sum of consecutive pairs from sorted desc list,
// treating it as a cycle: vals[0]*vals[1] + vals[1]*vals[2] + ... + vals[n-1]*vals[0]
// where vals is sorted descending. This is: vals[0]*(vals[1]+vals[n-1]) + (inner pairs)
// This might not be optimal. Let me use the established result:
// For any graph where nodes have degree at most 2, sort and assign greedily.
//
// Since this is complex, let me just find the structure and compute.
let _ = vals;
score_cycle(n)
} else {
// Path: m = n-1
// Find endpoints (degree 1)
score_path(n)
}
}
}
fn score_path(n: usize) -> i64 {
// For a path of n nodes, maximum sum of adjacent products:
// Assign n to one end-neighbor, n-1 to the other end-neighbor, etc.
// Optimal assignment for path:
// Place largest values at positions 2, 3 (0-indexed from end) so they appear in 2 edges each.
// Known result: sort values descending [n, n-1, n-2, ...]
// Place them: position 2, position 3, position 4, ..., then 0, 1 at the ends
// Score = n*(n-1) + n*(n-2) + (n-1)*(n-3) + ... this gets complex.
//
// Actually the well-known result:
// For path with values 1..n, arrange as: 2,4,6,...,n (or n-1 if odd), ..., 1,3,5,...
// But the proven maximum for a path is just: assign greedily.
//
// Simpler proven formula: for a path of n nodes,
// max score = n*(n-1) + (n-2)*(n-3) + ...
// This pairs up from the top, which gives floor(n/2) products.
// But a path has n-1 edges! So this can't be right for n > 2.
//
// OK let me just think more carefully.
// Path: v0 - v1 - v2 - ... - v(n-1)
// Score = sum_{i=0}^{n-2} a[i]*a[i+1]
//
// It's known that for a path, the optimal assignment puts the two largest values
// at the two nodes adjacent to the center (maximizing their contribution to 2 edges each).
//
// In fact, for the standard "maximize sum of products of adjacent pairs in a permutation"
// on a path, the greedy is: place values in pattern ..., 3, 1, 4, 2, 5, ...
//
// For n=4: values [1,2,3,4]. Optimal: 1,3,4,2 -> 3+12+8=23 ✓ (example output)
// Pattern: 1*(n/2 round), ...: actually [1,3,4,2] which is: small, big, big, small
// Score = 1*3 + 3*4 + 4*2 = 3+12+8=23
// Another: [2,4,3,1] -> 8+12+3=23
// The formula for path: pair up from top (n * (n-1)) + ((n-2)*(n-3)) + ...
// = 4*3 + 2*1 = 12+2=14? No, that's 14 but answer is 23.
//
// So my formula was wrong. The correct optimal for path is NOT pairing.
//
// Correct approach for path: place the two largest values at the two middle positions
// (positions n/2-1 and n/2 for even n). The next two at their neighbors, etc.
//
// Alternatively: for a path of length n, the maximum is achieved by:
// sorted descending: a1 >= a2 >= ... >= an
// Score = a1*(a2+a3) + a2*(a4+a5) + ... (roughly)
//
// Exact formula for path:
// Arrange as: a_n, a_(n-2), a_(n-4), ..., ..., a_(n-3), a_(n-1)
// Nope this is getting complicated. Let me just compute it for small n and find pattern.
//
// n=2: [1,2] -> score=2
// n=3: [1,2,3] best is 1,3,2 -> 3+6=9 or 2,3,1->6+3=9
// n=4: [1,2,3,4] best is 23 (example)
// n=5: max from [1,2,3,4,5]? Try 2,4,5,3,1 -> 8+20+15+3=46
// or 1,4,5,3,2 -> 4+20+15+6=45
// or 1,3,5,4,2 -> 3+15+20+8=46
// or 2,5,4,3,1 -> 10+20+12+3=45
// or 1,4,5,2,3 -> 4+20+10+6=40
// max seems 46 for n=5?
// Pattern for max:
// n=2: 2 = 1*2
// n=3: 9 = 1*3 + 3*2 = 3+6 (or 2*3+3*1)
// n=4: 23 = 1*3+3*4+4*2 = 3+12+8
// n=5: 46 = 2*4+4*5+5*3+3*1 or 1*3+3*5+5*4+4*2 = 3+15+20+8=46
//
// For path, the optimal: place values such that the largest value has 2 neighbors,
// second largest has 2 as well, ..., until only 2 values left at ends.
// Values at interior positions contribute to 2 edges, ends contribute to 1 edge.
//
// Interior positions: n-2 nodes, each in 2 edges. End positions: 2 nodes, each in 1 edge.
// To maximize: assign n largest values to interior, 2 smallest to ends.
// But for n=4: interior=[2 pos], ends=[2 pos]. Assign {3,4} to interior, {1,2} to ends.
// Score: end1 * int1 + int1 * int2 + int2 * end2
// = 1*3 + 3*4 + 4*2 = 3+12+8=23 ✓
// For n=5: interior=[3 pos], ends=[2 pos]. Assign {3,4,5} to interior, {1,2} to ends.
// Score: 1*? + various. The 3 interior in order: to maximize, put largest in middle.
// 1 * 3 + 3 * 5 + 5 * 4 + 4 * 2 = 3+15+20+8=46 ✓
//
// For general path: assign values n, n-1, ..., 3 to interior positions (from center out),
// and values 1, 2 to the two ends.
// Interior: arrange as ..., n-4, n-2, n, n-1, n-3, n-5, ...
// (largest in center, alternating)
// Score = 2 * (n*(n-1) + ) ... complex.
//
// Actually: for path of n, the optimal score is:
// sum_{i=2}^{n} i*(i-1) - (n-1) ... no.
//
// Let me just implement the greedy: keep track of available values and a deque,
// place largest remaining in the interior.
//
// For a path of n with optimal assignment:
// Assign: interior positions (n-2 of them) get values n, n-1, ..., 3 arranged as "zigzag"
// Ends get 1 and 2.
// Score = sum_edges products.
//
// Given the structure is a path/cycle of <=5*10^4 nodes, perfect info:
// - Find endpoints of the path (degree 1 nodes)
// - Assign values greedily: the center interior gets largest, etc.
//
// But this depends on the specific path layout. Key insight:
// The actual structure of the graph doesn't matter for the optimal value calculation --
// only whether it's a path or a cycle, because we can rearrange values along the path/cycle.
//
// For path of n: optimal score = ?
// Let's compute formula:
// Arrange: ends get val_low1, val_low2; interior positions filled with val_high values.
// Interior has n-2 positions. To maximize, put the largest value second from one end,
// since it multiplies with the end value AND the next interior value.
//
// Actually, the overall result is achieved by the following known algorithm:
// Sort values. Assign 2 smallest to ends, rest to interior.
// Within interior, arrange the n-2 interior values to maximize sum of n-3 interior products
// plus 2 boundary products (with the end values 1 and 2).
// This is a recursive problem.
//
// Known formula for path:
// score = n*(n-1)/2 * 2 - something??
//
// I'll use a different approach: compute for path and cycle using the known greedy:
// For a path: assign values to nodes in order of degree contribution.
// Since each interior node contributes product to 2 edges, endpoints to 1:
// Effective weight of node = (number of edges it participates in)
// Interior nodes: 2 edges, endpoints: 1 edge
//
// This doesn't directly give an assignment formula.
//
// Let me just directly compute: for a path, the answer is:
// sum_{i=1}^{n-1} a_i * a_{i+1} maximized over permutations.
//
// Claim: optimal = arrange in pattern low, high, high, low, low, high, high, ...
// Actually no. For n=4, [1,3,4,2] achieves 23. This is: small, big, big, small.
//
// For n=6: try [1,3,5,6,4,2] -> 3+15+30+24+8=80
// try [2,4,6,5,3,1] -> 8+24+30+15+3=80
// try [1,4,6,5,3,2] -> 4+24+30+15+6=79 < 80
// try [1,3,6,5,4,2] -> 3+18+30+20+8=79
// [1,3,5,6,4,2]=80? 1*3+3*5+5*6+6*4+4*2=3+15+30+24+8=80
// [2,4,6,5,3,1]=8+24+30+15+3=80
// [1,4,5,6,3,2]=4+20+30+18+6=78
// [2,5,6,4,3,1]=10+30+24+12+3=79
// Seems 80 for n=6.
//
// Formula check: for n=6, my formula gives:
// Path n=6: two smallest (1,2) at ends, largest (6) in middle, ...
// Score sequence: 1, 3, 5, 6, 4, 2 -> check again: 3+15+30+24+8=80 ✓
// Values at positions: {1,2} at ends, {3,4,5,6} at interior in order 3,5,6,4
// Interior pattern: ..., 3, 5, 6, 4, ... (ascending then descending "tent")
//
// For n positions, arrange interior as: vals from 3 to n in tent pattern,
// then edges at boundary with 1 and 2.
//
// Simpler: the score for optimal path is computed as follows:
// Let sorted vals = [1, 2, 3, ..., n].
// Score = n*(n-1) + (n-2)*(n-1) + sum of interior products
// Hmm not clear.
//
// OK, I'll use a direct computation: given n, compute the optimal directly.
// For path: optimal = score of sequence: 2, 4, 6, ..., n (or n-1), ..., 5, 3, 1
// i.e., even indices first (ascending), then odd indices (descending)?
// n=4: [2,4,3,1]->8+12+3=23 ✓
// n=5: [2,4,5,3,1]->8+20+15+3=46 ✓?
// [2,4,5,3,1]: 8+20+15+3=46 ✓
// n=6: [2,4,6,5,3,1]->8+24+30+15+3=80 ✓
// n=3: [2,3,1]->6+3=9 ✓
// n=2: [2,1]->2 ✓
//
// Pattern: [2, 4, 6, ..., (n if even, n-1 if odd), ..., 5, 3, 1]
// i.e., even numbers ascending then odd numbers descending (or similar)
//
// Let me verify for n=7: [2,4,6,7,5,3,1]->8+24+42+35+15+3=127
// [2,4,6,7,5,3,1] = 8+24+42+35+15+3=127
// vs [1,3,5,7,6,4,2]= 3+15+35+42+24+8=127 same
//
// So for a path of n, optimal score = score of [2,4,6,...,n,n-1,...,3,1] (or similar)
// = sum of products of consecutive elements in this sequence.
//
// Actually this is complex to formula-ize. Let me just compute it directly:
// Build the sequence and sum up products.
let mut seq = Vec::with_capacity(n);
// even indices: 2, 4, 6, ... up to n (or n-1)
let mut i = 2usize;
while i <= n {
seq.push(i as i64);
i += 2;
}
// odd indices (starting from n or n-1 down): n-1 or n (whichever odd), ..., 3, 1
let start_odd = if n % 2 == 0 { n - 1 } else { n };
let mut i = start_odd;
loop {
seq.push(i as i64);
if i < 2 { break; }
i -= 2;
}
// Drop the last 0 if any
seq.retain(|&x| x > 0);
seq.windows(2).map(|w| w[0] * w[1]).sum()
}
fn score_cycle(n: usize) -> i64 {
// For a cycle of n: same type of arrangement but it's circular.
// Pattern: [2,4,6,...,n,n-1,...,3,1] as a cycle.
// Known: for cycle, optimal is same as path but last element connects to first.
// For n=6 example output is 82. Let me verify with cycle formula.
// n=6 cycle: [2,4,6,5,3,1] as cycle -> 8+24+30+15+3+(1*2)=8+24+30+15+3+2=82 ✓
// So use same sequence as path but add the last*first product.
let mut seq = Vec::with_capacity(n);
let mut i = 2usize;
while i <= n {
seq.push(i as i64);
i += 2;
}
let start_odd = if n % 2 == 0 { n - 1 } else { n };
let mut i = start_odd;
loop {
seq.push(i as i64);
if i < 2 { break; }
i -= 2;
}
seq.retain(|&x| x > 0);
let path_score: i64 = seq.windows(2).map(|w| w[0] * w[1]).sum();
path_score + seq[0] * seq[n - 1]
}