เพิ่มผลรวมผลคูณดีกรีระหว่างจุดยอดในต้นไม้ใน C++

ภาพรวมปัญหา

สร้างต้นไม้ (Tree) ขนาด N ให้ผลรวมของ degree(x) × degree(y) สำหรับทุกคู่มี序 (x,y) โดย x≠y มีค่าสูงสุด

ตัวอย่าง

Input: N = 5
Output: 50
Tree: 1-2-3-4-5 (Path graph)
Degrees: 1,2,2,2,1
Sum = 50

Input: N = 7
Output: 122

แนวทางแก้ปัญหา

• ผลรวมดีกรีทั้งหมดในต้นไม้ = 2N - 2
• เพื่อให้ผลคูณสูงสุด ต้องลดจำนวนใบ (leaf nodes) ให้น้อยที่สุด
• โครงสร้าง Path Graph (เส้นตรง) ให้ผลลัพธ์สูงสุด

ตัวอย่างโค้ด C++

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

int Max(int N) {
    int sum = 0;
    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= N; y++) {
            if (x == y) continue;
            int degreeX = (x == 1 || x == N) ? 1 : 2;
            int degreeY = (y == 1 || y == N) ? 1 : 2;
            sum += (degreeX * degreeY);
        }
    }
    return sum;
}

int main() {
    int N = 5;
    cout << Max(N);
    return 0;
}

ผลลัพธ์

50