🔍 核心问题分析

题目要求计算路径上点集的最小线性拟合误差。简单来说：

• 每个行星系对应二维平面上的点 $(C_i, D_i)$
• 需要找到一条路径，使得路径上所有点到某条直线的欧几里得距离平方和最小
• 输出这个最小值作为非可疑度

🧮 关键思路：数学推导

1. 直线拟合与距离计算

设直线方程为 $y = kx + b$，点到直线的距离平方和为：

$$\delta = \sum \frac{(kx_i - y_i + b)^2}{k^2 + 1}$$

2. 最优参数求解

通过求导可得最优 $b$ 为：

$$b = \frac{\sum y_i}{n} - k \frac{\sum x_i}{n} = \bar{y} - k\bar{x} $$

代入原式并化简后，得到最小相斥度的表达式：

$$\delta_{\min} = \min \left\{ \frac{A + C - \sqrt{(A+C)^2 - 4(AC-B^2)}}{2} \right\} $$

其中：

• $A = \sum x_i^2 - \frac{(\sum x_i)^2}{n}$
• $B = \sum x_iy_i - \frac{\sum x_i \sum y_i}{n}$
• $C = \sum y_i^2 - \frac{(\sum y_i)^2}{n}$

⚙️ 算法实现

数据结构设计

需要维护六个关键变量：

• $\sum x$（$C_i$ 的和）
• $\sum y$（$D_i$ 的和）
• $\sum x^2$（$C_i^2$ 的和）
• $\sum y^2$（$D_i^2$ 的和）
• $\sum xy$（$C_iD_i$ 的和）
• $n$（点的个数）

图结构处理

根据题意 $M \leq N$，图可能是树或基环树。

对于树的情况：

• 以节点1为根进行DFS预处理
• 使用树上差分：路径信息 = $a_u + a_v - a_{lca} - a_{fa[lca]}$
• 通过LCA（树链剖分）快速求路径信息

对于基环树的情况：

1. 找出环上的一条边
2. 对于查询 $(u, v)$，如果 $u, v$ 在同一个子树，按树的方法处理
3. 否则，有两条可能路径，取最小值

💻 代码框架

#include <bits/stdc++.h>
using namespace std;

struct Node {
    double s1, s2, s3, s4, s5; // ∑x, ∑y, ∑x², ∑y², ∑xy
    int cnt;
    
    Node operator + (const Node& t) const {
        return {s1+t.s1, s2+t.s2, s3+t.s3, s4+t.s4, s5+t.s5, cnt+t.cnt};
    }
    
    Node operator - (const Node& t) const {
        return {s1-t.s1, s2-t.s2, s3-t.s3, s4-t.s4, s5-t.s5, cnt-t.cnt};
    }
    
    double calc() {
        double A = s3 - s1*s1/cnt;
        double B = s5 - s1*s2/cnt; 
        double C = s4 - s2*s2/cnt;
        return (A + C - sqrt((A+C)*(A+C) - 4*(A*C-B*B))) / 2;
    }
};

// 树链剖分求LCA
// 基环树找环
// 预处理每个点到根的信息

📊 复杂度分析

• 预处理：$O(N)$ DFS
• 查询：$O(\log N)$ 求LCA和路径信息
• 总复杂度：$O(N + Q\log N)$，可以处理 $10^5$ 的数据规模

💎 总结

这道题的解题关键在于：

1. 数学推导出最小线性拟合误差的表达式
2. 维护六个统计量来快速计算任意路径的拟合误差
3. 利用树上差分处理路径查询
4. 分类讨论树和基环树的情况