C++で木の任意の2頂点間の次数の積の合計を最大化する

問題概要

整数Nが与えられたとき、N個の頂点を持つ木を構築し、すべての順序付きペア(x, y)（ただしx ≠ y）に対する degree(x) × degree(y) の合計が最大になるようにするのが本記事の目的です。

入力: N = 5

出力: 50

計算例

葉の数を最小限に抑えた木は、次のような鎖状（パス）の構造になります。

1 - 2 - 3 - 4 - 5

各頂点の次数は次のとおりです。

頂点1の次数 = 1
頂点2の次数 = 2
頂点3の次数 = 2
頂点4の次数 = 2
頂点5の次数 = 1

すべての順序付きペア(x, y)に対する次数の積は以下のように計算できます。

頂点1 = 1×2 + 1×2 + 1×2 + 1×1 = 7
頂点2 = 2×1 + 2×2 + 2×2 + 2×1 = 12
頂点3 = 2×1 + 2×2 + 2×2 + 2×1 = 12
頂点4 = 2×1 + 2×2 + 2×2 + 2×1 = 12
頂点5 = 1×2 + 1×2 + 1×2 + 1×1 = 7
合計 = 50

入力: N = 7

出力: 122

解法のアプローチ

• 木に含まれるすべての頂点の次数の合計は 2N − 2 になります（Nは頂点数）。この合計を最大化するには、葉（次数1の頂点）の数を最小化する必要があります。
• Max() 関数内で sum を 0 で初期化し、x と y について二重ループを作成します。
• ループ内では、まず x == y であるかを判定し、該当する場合は continue でスキップします。
• それ以外の場合、degreeX を 2 で初期化し、x が葉または根（x == 1 または x == N）であれば degreeX を 1 に設定します。y についても同様に degreeY を求めます。
• 最後に sum += (degreeX * degreeY) で合計を更新し、ループ終了後に結果を返します。

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;
            // 頂点xの次数を2で初期化
            int degreeX = 2;
            // xが葉または根の場合
            if (x == 1 || x == N)
                degreeX = 1;
            // 頂点yの次数を2で初期化
            int degreeY = 2;
            // yが葉または根の場合
            if (y == 1 || y == N)
                degreeY = 1;
            // 合計を更新
            sum += (degreeX * degreeY);
        }
    }
    return sum;
}

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

出力結果

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

50

補足: O(1)で求める数式

この問題は数式を使えば定数時間で解くことも可能です。次数が「1, 2, 2, …, 2, 1」となるパス状の木では、次数の総和は 2N − 2、次数の2乗の総和は 2×1² + (N−2)×2² = 4N − 6 となります。順序付きペア全体の積の総和は「(次数の総和)² − (次数の2乗の総和)」で表されるため、次の式が成り立ちます。

答え = (2N − 2)² − (4N − 6) = 4N² − 12N + 10

N = 5 の場合は 4×25 − 60 + 10 = 50、N = 7 の場合は 196 − 84 + 10 = 122 となり、実際の結果と一致することを確認できます。