Tối đa hóa tổng tích bậc giữa các cặp đỉnh của cây trong C++

Cho số nguyên N (số đỉnh). Xây dựng cây N đỉnh sao cho tổng Σ degree(x) * degree(y) cho mọi cặp có thứ tự (x, y) với x ≠ y là lớn nhất.

Ví dụ

N = 5 → Output: 50
Cây dạng đường (path): 1-2-3-4-5
Bậc: deg(1)=1, deg(2)=2, deg(3)=2, deg(4)=2, deg(5)=1
Tổng = 50

N = 7 → Output: 122

Phân tích

Tổng bậc của cây = 2(N-1). Để tối đa hóa tổng tích bậc, cần giảm thiểu số nút lá (bậc 1). Cây đường (path) chỉ có 2 nút lá, các nút còn lại bậc 2 → tối ưu.

Với cây đường: 2 nút bậc 1, (N-2) nút bậc 2.

Tổng cần tính: Σ_{x≠y} deg(x)deg(y) = (Σ deg(x))² - Σ deg(x)².

• Σ deg = 2N-2
• Σ deg² = 2*1² + (N-2)*2² = 2 + 4N - 8 = 4N - 6
• Kết quả = (2N-2)² - (4N-6) = 4N² - 8N + 4 - 4N + 6 = 4N² - 12N + 10

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

long long maxDegreeProductSum(int N) {
    if (N <= 1) return 0;
    // Công thức: 4N² - 12N + 10
    return 4LL * N * N - 12LL * N + 10;
}

int main() {
    int N = 5;
    cout << maxDegreeProductSum(N); // Output: 50
    return 0;
}

Kết quả

50

Lưu ý

Code gốc trong bài dùng vòng lặp O(N²) tính trực tiếp. Công thức O(1) trên nhanh hơn và đúng cho mọi N ≥ 2.