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

เนื่องจากภารกิจคือการสร้างทรีด้วยจำนวนเต็ม N ที่กำหนด ดังนั้นผลรวมของ degree(x) * degree(y) สำหรับคู่ที่เรียงลำดับทั้งหมด (x,y) จะสูงสุด และ x ไม่เท่ากับ y

ป้อนข้อมูล −N=5

ผลผลิต −50

คำอธิบาย

   1
    \
     2
      \
       3
         \
          4
            \
             5
Degree of 1st node = 1
Degree of 2nd node = 2
Degree of 3rd node = 2
Degree of 4th node = 2
Degree of 5th node = 1

ผลิตภัณฑ์ของทุกองศาสำหรับคู่ที่สั่งซื้อทั้งหมด (x, y) −

1st node = 1*2 + 1*2 + 1*2 + 1*1 = 7
2nd node = 2*1 + 2*2 + 2*2 + 2*1 = 12
3rd node = 2*1 + 2*2 + 2*2 + 2*1 = 12
4th node = 2*1 + 2*2 + 2*2 + 2*1 = 12
5th node = 1*2 + 1*2 + 1*2 + 1*1 = 7
Total sum = 50

ป้อนข้อมูล −N=7

ผลผลิต −122

แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้

ผลรวมขององศาของโหนดทั้งหมดในทรีคือ − (2 * N) – 2 ในที่นี้ N=จำนวนโหนดในทรี เพื่อเพิ่มผลรวมสูงสุด จำนวนของโหนดปลายสุดต้องถูกย่อให้เล็กสุด
ฟังก์ชัน Inside Max() เริ่มต้น int sum=0 และสร้างลูปซ้อนเริ่มต้น x=1 และ y=1 มีเงื่อนไข x
ภายในลูปที่ซ้อนกันก่อนตรวจสอบว่า (x==y) ถ้าเป็นเช่นนั้นให้เพิ่มต่อไป แถลงการณ์
อื่นเริ่มต้น int องศา =2 และใช้คำสั่ง if ตรวจสอบ if(x==1 || x==n) ถ้าใช่ ให้ใส่ degreeX=1 จากนั้นเริ่มต้น int degree=2 และทำเช่นเดียวกันกับตัวแปร y
สุดท้าย ก่อนปิดลูป ให้อัปเดตตัวแปร sum โดยเขียน − sum =(degreeX + degreeY)

ตัวอย่าง

#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;
         //Initializing degree for node x to 2
         int degreeX = 2;
         //If x is the leaf node or the root node
         if (x == 1 || x == N)
            degreeX = 1;
         //Initializing degree for node y to 2
         int degreeY = 2;
         //If y is the leaf node or the root node
         if (y == 1 || y == N)
            degreeY = 1;
         //Updating sum
         sum += (degreeX * degreeY);
      }
   }
   return sum;
}
//Main function
int main(){
   int N = 5;
   cout << Max(N);
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -