C++でツリーの任意の2つの頂点間の度の積の合計を最大化します

   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=ツリー内のノードの数です。合計を最大化するには、リーフノードの数を最小化する必要があります。

• Max（）関数内で、int sum =0を初期化し、条件x

• ネストされたループ内で、最初にif（x ==y）をチェックし、そうであれば、続行を追加します。ステートメント

• それ以外の場合は、intdegree =2を初期化し、ifステートメントを使用してif（x ==1 || x ==n）をチェックします。もしそうなら、degreeX=1を置きます。次に、intdegree =2を初期化し、変数y

  に対して同じことを行います。

• 最後に、ループを閉じる前に、次のように合計変数を更新します。− 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);
}

出力

上記のコードを実行すると、次の出力が得られます-

50