思路与算法

令x_i为树位置，B_i为重量前缀，W_i为重量乘位置前缀。第一站i前费用one_i=x_iB_i-W_i。第二站i前转移one_j+W_j-x_iB_j+x_iB_i-W_i，枚举j<i；以直线(-B_j,one_j+W_j)维护最小。第二站后余树统一送固定山脚x_{n+1}，逐i补尾段费用取小。

正确性说明

正好两个新增厂将树按下山方向分成三段，每棵树送最近下方厂不会更差，所列前缀公式准确求段成本。先查询后加入直线保证两座新增厂不同且顺序正确。重量为正使斜率严格递减，位置非降使查询单调，双端凸包删除的线以后都不会最优。

复杂度

前缀初始化、每条线进出队及查询总O(n)时间，O(n)空间。费用用64位，交点叉乘用128位避免比较溢出。

易错点

距离可为0，重复查询坐标仍合法。山脚是固定第三厂，不要误变为可任意放三个新厂。n=2时两棵树均可设厂，运输费用为0。输入新增大规模部分按题定64位保证处理。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct L {
    ll m, b;
};
__int128 val(L l, ll x) {
    return (__int128)l.m * x + l.b;
}
void insertL(deque<L> &h, L z) {
    while (h.size() > 1) {
        L a = h[h.size() - 2], b = h.back();
        if ((__int128)(b.b - a.b) * (b.m - z.m) >= (__int128)(z.b - b.b) * (a.m - b.m))
            h.pop_back();
        else
            break;
    }
    h.push_back(z);
}
ll query(deque<L> &h, ll x) {
    while (h.size() > 1 && val(h[0], x) >= val(h[1], x))
        h.pop_front();
    return (ll)val(h.front(), x);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> x(n + 2), B(n + 1), W(n + 1), one(n + 1), two(n + 1);
    for (int i = 1; i <= n; i++) {
        ll w, d;
        cin >> w >> d;
        B[i] = B[i - 1] + w;
        W[i] = W[i - 1] + w * x[i];
        x[i + 1] = x[i] + d;
    }
    deque<L> h;
    const ll INF = LLONG_MAX;
    ll ans = INF;
    for (int i = 1; i <= n; i++) {
        one[i] = x[i] * B[i] - W[i];
        if (!h.empty()) {
            two[i] = x[i] * B[i] - W[i] + query(h, x[i]);
            ll tail = x[n + 1] * (B[n] - B[i]) - (W[n] - W[i]);
            ans = min(ans, two[i] + tail);
        }
        insertL(h, {-B[i], one[i] + W[i]});
    }
    cout << ans << '\n';
}