好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：CEOI 2004

从山顶上到山底下沿着一条直线种植了 $n$ 棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。

木材只能朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建这两个锯木厂，使得运输的费用总和最小。假定运输每公斤木材每米需要一分钱。

你的任务是编写一个程序，读入树的个数和他们的重量与位置，计算最小运输费用。

---

输入格式

输入的第一行为一个正整数 $n$，表示树的个数。树从山顶到山脚按照 $1,2,\dots,n$ 标号。

接下来 $n$ 行，每行有两个整数 $w_i$ 和 $d_i$。分别表示第 $i$ 棵树的重量（公斤为单位）和第 $i$ 棵树和第 $i+1$ 棵树之间的距离。最后一个数 $d_n$，表示第 $n$ 棵树到山脚的锯木厂的距离。

---

输出格式

输出一行一个整数，表示最小的运输费用。

---

样例

样例输入

9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

样例输出

26

样例说明

下图展示了对于样例输入的最佳伐木场设置位置（原题附图）。运输费用总和为 $26$。

---

数据范围

• 对于 $97$ 分的数据，$2 \le n \le 2\times 10^4, 1 \le w_i \le 10^4, 0 \le d_i \le 10^4$，保证所有树运到山脚的锯木厂所需要的费用小于 $2\times 10^9$ 分。
• 对于另外 $3$ 分的数据，$2 \le n \le 2\times 10^5$，保证所有计算均可在 $64$ 位有符号整数下进行。

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$32768 \text{ KB}$（注意此题内存限制较小，为 32 MB）

---

提示
此题为 斜率优化 DP 经典题。

问题转化： 设树 $i$ 到山脚（锯木厂 $n+1$）的距离为 $D_i$（即从山顶到树 $i$ 的距离前缀和加上 $i$ 到山脚的距离）。
具体地，设 $d_i$ 表示树 $i$ 到树 $i+1$ 的距离（$i=n$ 时 $d_n$ 表示树 $n$ 到山脚的距离）。
则树 $i$ 到山脚的距离 $D_i = \sum_{k=i}^n d_k$（其中 $d_k$ 为 $k$ 到 $k+1$ 的距离，$d_n$ 为树 $n$ 到山脚距离）。

如果我们在位置 $i$ 和 $j$（$i < j$）建立两个锯木厂，则：

• 树 $1 \dots i$ 运到锯木厂 $i$；
• 树 $i+1 \dots j$ 运到锯木厂 $j$；
• 树 $j+1 \dots n$ 运到山脚锯木厂（位置 $n+1$）。

总运输费用为：

$$\text{cost}(i,j) = \sum_{k=1}^i w_k \cdot (D_k - D_i) + \sum_{k=i+1}^j w_k \cdot (D_k - D_j) + \sum_{k=j+1}^n w_k \cdot D_k$$

预处理： 设 $sumW[i] = \sum_{k=1}^i w_k$，$sumWD[i] = \sum_{k=1}^i w_k \cdot D_k$。

则总费用可以表示为：

$$\text{cost}(i,j) = \left( sumWD[i] - D_i \cdot sumW[i] \right) + \left( (sumWD[j] - sumWD[i]) - D_j \cdot (sumW[j] - sumW[i]) \right) + \left( sumWD[n] - sumWD[j] \right)$$

简化得：

$$\text{cost}(i,j) = sumWD[n] - D_i \cdot sumW[i] - D_j \cdot (sumW[j] - sumW[i])$$

因此我们需要最小化：

$$f(i,j) = -D_i \cdot sumW[i] - D_j \cdot (sumW[j] - sumW[i])$$

即最大化：

$$g(i,j) = D_i \cdot sumW[i] + D_j \cdot (sumW[j] - sumW[i])$$

固定 $i$ 优化 $j$： 对于固定的 $i$，$D_i \cdot sumW[i]$ 是常数，我们需要最大化 $D_j \cdot (sumW[j] - sumW[i])$，即 $D_j \cdot sumW[j] - D_j \cdot sumW[i]$。

设 $X_j = sumW[j]$, $Y_j = D_j \cdot sumW[j]$，则对于固定 $i$，需要最大化 $Y_j - D_j \cdot sumW[i]$。

这是斜率优化形式：$Y_j - k_i X_j$，其中 $k_i = sumW[i]$。

由于 $sumW[i]$ 单调递增，$X_j$ 单调递增，可以用单调队列维护上凸包（求最大值）。

枚举 $i$： 我们可以枚举第一个锯木厂位置 $i$，然后快速找到最优的第二个锯木厂位置 $j$（$j > i$）。

步骤：

1. 预处理 $D_i$（后缀和），$sumW[i]$, $sumWD[i]$；
2. 从后往前维护一个单调队列（上凸包），用于对每个 $i$ 查询最优 $j$（$j > i$）；
3. 枚举 $i$ 从 $1$ 到 $n-2$（因为至少两个锯木厂且 $j>i$，且山脚已有锯木厂），用队列求出最优 $j$，更新答案；
4. 注意总费用公式中的常数项 $sumWD[n]$。

复杂度：$O(n)$。

注意：

• 由于 $w_i$ 和 $d_i$ 较大，计算过程中要用 long long；
• 队列维护时注意 $j$ 的范围（$j>i$）；
• 可以预处理 $h[i] = D_i \cdot sumW[i]$ 等简化计算。