C++で木の辺に重みを割り当て、重みの総和が最大となるパスを最小化する方法

問題の概要

ここでは、木（ツリー構造）に関する興味深い問題を取り上げます。木とその辺の重みの総和 S が与えられたとき、残りのすべての辺に重みを割り当てることを考えます。条件は、割り当てた重みの合計がちょうど S になること、そして重みの観点で最長となるパスの長さをできる限り小さくすることです。

解法のアプローチ

この問題の鍵となるのは、木の基本的な性質です。木の中の任意のパスに含まれる葉（リーフ）ノードは、最大で2つまでという点です。この性質を活用すれば、シンプルに最適な解を導き出すことができます。

具体的な戦略は次のとおりです。

• 葉ノードに直接接続している辺だけに重みを割り当てる
• それ以外の辺にはすべて 0 を割り当てる

このようにすると、葉に接続するそれぞれの辺には、次の値が割り当てられます。

S ÷ count　※count は葉ノードの総数

1本のパスには最大2つの葉しか含まれないため、最終的な最長パスの長さは次の式で求められます。

2 × S ÷ count

C++による実装例

#include<iostream>
#include<vector>
using namespace std;

void insertEdge(int u, int v, vector<int> adj[]) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

long double pathLength(vector<int> adj[], int sum, int n) {
    int count = 0;
    // 隣接リストのサイズが1のノード＝葉ノードをカウント
    for (int i = 1; i <= n; i++) {
        if (adj[i].size() == 1)
            count++;
    }
    // 最長パス = 2 × S ÷ count
    long double ans = 2.0 * (long double)(sum / (long double)(count));
    return ans;
}

int main() {
    int n = 6;
    vector<int> adj[n + 1];
    insertEdge(1, 2, adj);
    insertEdge(2, 3, adj);
    insertEdge(2, 4, adj);
    insertEdge(4, 5, adj);
    insertEdge(4, 6, adj);
    int sum = 1;
    cout << pathLength(adj, sum, n);
}

実行結果

0.5

コードのポイント

このプログラムでは、隣接リストを使って木を表現しています。隣接するノードが1つだけの頂点は葉ノードであるため、それらを数え上げることで count を求めています。あとは先述の公式どおり 2 × S ÷ count を計算するだけで、最短化された最長パスの長さが得られます。

この手法の計算量は O(n) であり、木全体を一度走査するだけで済むため、大規模な木に対しても効率的に動作します。