概要

地点 \(i\) 宛ての手紙は、必ず郵便局から地点 \(i\) までの \(i-1\) 本の辺を、手元に持った状態で通過します。したがって、各手紙の疲労度への寄与を独立に考えれば、答えは \(\sum_{i=2}^{N} B_i(i-1)\) です。

考察

手紙 1 通が発生させる疲労度

地点 \(i\) 宛ての手紙を 1 通考えます。

この手紙は地点 \(1\) にある郵便局から出発し、届け先である地点 \(i\) まで運ばなければなりません。そのため、少なくとも次の \(i-1\) 回の移動中は手元に持っている必要があります。

• 地点 \(1 \to 2\)
• 地点 \(2 \to 3\)
• \(\ldots\)
• 地点 \(i-1 \to i\)

各移動では、手元にある手紙 1 通につき疲労度が \(1\) 発生します。よって、地点 \(i\) 宛ての手紙 1 通が発生させる疲労度は、少なくとも

\[ i-1 \]

です。

地点 \(i\) 宛ての手紙は \(B_i\) 通あるため、それらによる疲労度は少なくとも

\[ B_i(i-1) \]

となります。

この下限は実現できる

すべての手紙を 1 回のルートで持ち出し、各地点に到着した時点でその地点宛ての手紙をすべて届けることを考えます。

1 回で持てる手紙の通数には上限がないため、この方法は常に可能です。それぞれの手紙は届け先までの辺をちょうど 1 回ずつ通り、それ以降は手元からなくなります。

したがって、各手紙について疲労度をちょうど \(i-1\) にできるので、全体の最小値は

\[ \sum_{i=2}^{N} B_i(i-1) \]

です。

なお、複数のルートに分けても、この値より小さくすることはできません。各手紙が届け先まで移動しなければならない事実は変わらないからです。

具体例

例えば、地点 \(2\) 宛てが \(2\) 通、地点 \(4\) 宛てが \(1\) 通の場合を考えます。

• 地点 \(2\) 宛ての手紙: \(2 \times 1 = 2\)
• 地点 \(4\) 宛ての手紙: \(1 \times 3 = 3\)

したがって、最小疲労度は

\[ 2+3=5 \]

です。

実際にすべてを一度に持つと、各移動での疲労度は次のようになります。

• 地点 \(1 \to 2\): \(3\) 通持っているので \(3\)
• 地点 \(2\) で \(2\) 通届ける
• 地点 \(2 \to 3\): 残り \(1\) 通なので \(1\)
• 地点 \(3 \to 4\): 残り \(1\) 通なので \(1\)

合計は \(3+1+1=5\) です。

素朴な方法の問題点

手紙を 1 通ずつシミュレーションすると、手紙の総数が非常に多いため TLE になります。また、ルートの分け方を列挙する必要もありません。

重要なのはルート単位ではなく、各手紙が届け先までに何本の辺を通るかです。地点ごとに \(B_i(i-1)\) を計算すれば、直接答えを求められます。

アルゴリズム

1. answer = 0 とする。
2. \(i=2,3,\ldots,N\) の順に \(B_i\) を読み込む。
3. answer に \(B_i(i-1)\) を加える。
4. answer を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

答えは 64-bit 符号付き整数に収まりますが、途中の積 \(B_i(i-1)\) も long long で計算する必要があります。

コードでは i - 1LL とすることで、掛け算が確実に long long で行われるようにしています。また、\(B_i\) を順に読みながら加算するため、配列に保存する必要はありません。

ソースコード

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    long long answer = 0;
    for (int i = 2; i <= N; ++i) {
        long long B;
        cin >> B;
        answer += B * (i - 1LL);
    }

    cout << answer << '\n';
    return 0;
}

---

この解説は gpt-5.6-sol-high によって生成されました。