Overview

Letters addressed to location \(i\) must be carried from the post office to location \(i\), passing through \(i-1\) edges. Therefore, if we consider the contribution of each letter to the fatigue level independently, the answer is \(\sum_{i=2}^{N} B_i(i-1)\).

Analysis

Fatigue caused by a single letter

Consider a single letter addressed to location \(i\).

This letter starts from the post office at location \(1\) and must be delivered to its destination, location \(i\). Therefore, it must be carried during at least the following \(i-1\) movements:

• Location \(1 \to 2\)
• Location \(2 \to 3\)
• \(\ldots\)
• Location \(i-1 \to i\)

In each movement, carrying one letter increases the fatigue level by \(1\). Therefore, the fatigue caused by a single letter addressed to location \(i\) is at least

\[ i-1 \]

Since there are \(B_i\) letters addressed to location \(i\), the fatigue caused by them is at least

\[ B_i(i-1) \]

This lower bound is achievable

Consider carrying all letters at once in a single trip, delivering all letters addressed to each location as soon as we arrive there.

Since there is no limit on the number of letters we can carry at once, this approach is always possible. Each letter passes through the edges on the way to its destination exactly once, and is delivered immediately after.

Therefore, we can make the fatigue for each letter exactly \(i-1\), so the minimum total fatigue is

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

Note that even if we split the delivery into multiple trips, we cannot make the total fatigue smaller than this value. This is because the fact that each letter must be moved to its destination remains unchanged.

Example

For example, consider the case where there are \(2\) letters addressed to location \(2\) and \(1\) letter addressed to location \(4\).

• Letters addressed to location \(2\): \(2 \times 1 = 2\)
• Letters addressed to location \(4\): \(1 \times 3 = 3\)

Therefore, the minimum fatigue is

\[ 2+3=5 \]

Indeed, if we carry all of them at once, the fatigue for each movement is as follows:

• Location \(1 \to 2\): Carrying \(3\) letters, so \(3\)
• Deliver \(2\) letters at location \(2\)
• Location \(2 \to 3\): \(1\) letter remaining, so \(1\)
• Location \(3 \to 4\): \(1\) letter remaining, so \(1\)

The total is \(3+1+1=5\).

Issues with Naive Approaches

Simulating the delivery letter by letter will result in TLE (Time Limit Exceeded) because the total number of letters can be very large. Also, there is no need to enumerate different ways of splitting the trips.

What matters is not the individual trips, but how many edges each letter must pass through to reach its destination. By calculating \(B_i(i-1)\) for each location, we can directly find the answer.

Algorithm

1. Set answer = 0.
2. Read \(B_i\) in the order of \(i=2,3,\ldots,N\).
3. Add \(B_i(i-1)\) to answer.
4. Print answer.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\)

Implementation Details

The final answer fits within a 64-bit signed integer, but the intermediate product \(B_i(i-1)\) must also be calculated using long long.

In the code, using i - 1LL ensures that the multiplication is performed using long long. Additionally, since we add the values while reading \(B_i\) sequentially, there is no need to store them in an array.

Source Code

#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;
}

---

This editorial was generated by gpt-5.6-sol-high.