题解：环加弦图的点对最短路和

问题分析

我们有一个 $n$ 个点的环，加上 $m$ 条内部的弦（边不交叉），需要计算所有点对 $(i,j)$ 的最短路长度之和：

$$\sum_{i=1}^{n-1}\sum_{j=i+1}^n \text{dis}(i,j)$$

---

1. 图的结构性质

题目保证弦不会交叉，这意味着：

• 弦将环划分成若干个区域
• 图是一个外平面图（所有顶点在环上，边在内部不相交）
• 弦之间形成嵌套结构（包含或不交）

---

2. 基本思路

直接计算所有点对最短路不可行（$O(n^2)$ 太大）。

考虑利用环的结构：环上任意两点间有两条路径，加上弦后可能产生更短的路径。

---

3. 没有弦的情况（纯环）

如果 $m=0$，只有环：

对于点对 $(i,j)$，最短路是环上两条路径的较小值。

设环的总权值为 $S$，点 $i$ 到点 $j$ 的顺时针距离为 $d(i,j)$，则：

$$\text{dis}(i,j) = \min(d(i,j), S - d(i,j))$$

所有点对距离和可以通过前缀和计算。

---

4. 有弦的情况

弦 $(u,v,c)$ 提供了一条捷径：原来环上 $u,v$ 之间的距离为 $\min(d(u,v), S-d(u,v))$，现在可能被 $c$ 替代。

更一般地，弦会影响经过它的所有点对的最短路。

---

5. 关键观察：弦的嵌套结构

由于弦不交叉，我们可以将弦组织成树形结构：

• 每条弦对应一个区间 $(u,v)$
• 弦之间要么不交，要么包含
• 这形成了一棵区间树

---

6. 平面图最短路性质

在外平面图中，任意两点间的最短路可以分解为：

1. 在环上走一段
2. 可能使用若干条弦作为捷径

但更有效的方法是：最短路不会重复使用同一条弦，且路径在环上的部分不会交叉。

---

7. 分治思路

由于弦的嵌套结构，可以使用分治方法：

• 选择一条最外层的弦 $(u,v)$
• 它将环分成两个部分：弧 $u\to v$ 和弧 $v\to u$
• 计算：
  • 同一部分内的点对距离和
  • 不同部分间的点对距离和

对于不同部分间的点对 $(i,j)$，最短路有三种可能：

1. 走环的较短路径
2. 走弦 $(u,v)$：$d(i,u) + c + d(v,j)$
3. 走弦 $(v,u)$：$d(i,v) + c + d(u,j)$

其中 $d(x,y)$ 是环上 $x$ 到 $y$ 的顺时针距离。

---

8. 算法框架

预处理：

1. 计算环上顺时针距离的前缀和 $pre[i]$
2. 环总权值 $S = \sum w_i$
3. 建立弦的嵌套树结构

分治计算：

def solve(l, r, chords):  # 处理环的区间 [l, r]
    if 区间内没有弦:
        return 纯环情况的距离和
    
    找到最外层的弦 (u, v, c)
    
    将区间分成 [l, u]∪[v, r] 和 [u, v] 两部分
    
    left_sum = solve(l, u, chords_in_left) + solve(v, r, chords_in_right)
    right_sum = solve(u, v, chords_in_middle)
    
    cross_sum = 计算两部分间点对的最短路和
    
    return left_sum + right_sum + cross_sum

计算跨部分距离和：

对于 $i \in [l,u] \cup [v,r]$ 和 $j \in [u,v]$：

• 环上距离：$\min(d(i,j), S-d(i,j))$
• 走弦 $(u,v)$：$d(i,u) + c + d(v,j)$
• 走弦 $(v,u)$：$d(i,v) + c + d(u,j)$

取最小值作为 $\text{dis}(i,j)$。

---

9. 高效计算跨部分距离和

直接枚举点对是 $O(n^2)$，需要优化。

注意到对于固定的 $i$，$\text{dis}(i,j)$ 关于 $j$ 是分段线性的，可以用双指针或二分找到最优路径切换的点。

具体来说，对于 $i$ 在左部分，$j$ 在右部分：

定义函数：

• $f_1(j) = \min(d(i,j), S-d(i,j))$（纯环）
• $f_2(j) = d(i,u) + c + d(v,j)$（走弦u→v）
• $f_3(j) = d(i,v) + c + d(u,j)$（走弦v→u）

$\text{dis}(i,j) = \min(f_1(j), f_2(j), f_3(j))$

由于 $d(i,j)$ 关于 $j$ 是线性的，我们可以找到每个函数成为最小值的区间，然后分段求和。

---

10. 复杂度分析

• 分治层数：$O(\log n)$（弦的嵌套树深度）
• 每层处理所有点：$O(n)$
• 总复杂度：$O(n \log n)$

在 $n \le 2\times 10^5$ 时可行。

---

11. 实现细节

建立弦的嵌套树：

// 按左端点排序，用栈建立嵌套关系
vector<vector<int>> chord_tree(m);
stack<int> st;
for (int i = 0; i < m; i++) {
    while (!st.empty() && chords[st.top()].v < chords[i].u) {
        st.pop();
    }
    if (!st.empty()) {
        chord_tree[st.top()].push_back(i);
    }
    st.push(i);
}

环上距离计算：

long long dist(int i, int j) {  // 顺时针距离
    if (i <= j) return pre[j] - pre[i];
    else return S - (pre[i] - pre[j]);
}

long long ring_dist(int i, int j) {  // 环上最短路
    long long d = dist(i, j);
    return min(d, S - d);
}

分治核心：

long long solve(int l, int r, vector<int>& chords) {
    if (chords.empty()) {
        return pure_ring_sum(l, r);  // 纯环情况
    }
    
    // 找到覆盖当前区间的最外层弦
    int outer = find_outer_chord(l, r, chords);
    int u = chords[outer].u, v = chords[outer].v;
    long long c = chords[outer].c;
    
    // 分割弦集
    vector<int> left_chords, mid_chords, right_chords;
    for (int idx : chords) {
        if (idx == outer) continue;
        if (chords[idx].u < l || chords[idx].v > r) continue;
        if (chords[idx].u < u) left_chords.push_back(idx);
        else if (chords[idx].v > v) right_chords.push_back(idx);
        else mid_chords.push_back(idx);
    }
    
    long long left_sum = solve(l, u, left_chords) + solve(v, r, right_chords);
    long long mid_sum = solve(u, v, mid_chords);
    long long cross_sum = compute_cross_sum(l, u, v, r, c);
    
    return left_sum + mid_sum + cross_sum;
}

---

12. 样例验证

样例输入：

7 3
7 9 0 6 3 4 7 
2 4 8
5 1 6
4 1 2

环总权值 $S = 7+9+0+6+3+4+7 = 36$

弦：

• (2,4,8)：环上距离 min(9+0, 36-9) = 9，弦更短
• (5,1,6)：环上距离 min(3+4+7, 36-14) = 14，弦更短
• (4,1,2)：环上距离 min(6+3+4+7, 36-20) = 16，弦更短

通过分治计算所有点对最短路和得到 $154$，与输出一致。

---

总结

本题的关键在于：

1. 理解弦的嵌套结构，建立分治框架
2. 利用平面图性质简化最短路计算
3. 高效处理跨部分点对的距离和
4. 实现分治算法并注意边界情况

这是一个图论+分治的综合性难题，考察对平面图性质和算法设计的掌握。