思路与算法

一棵生成树对应点(Σu,Σv)。先用Kruskal找最小u与最小v的端点；对两点A,B用法向量(A.v-B.v,B.u-A.u)作为边权系数再求MST。若新点严格位于弦下则继续分割，得到所有相关下凸包顶点。查询正系数线性目标，在凸链上二分最小点并输出三位小数。

正确性说明

任一查询都是树代价点集的线性函数，最优值必在下凸包。法向量MST若没有严格低于弦的点，则弦之间没有遗漏的凸包顶点；若存在则两侧递归完整覆盖。凸链上的线性目标单峰，二分返回全局最小值。

复杂度

设实际发现H个极端点、边M、点N、查询Q。读入及初始化O(N+M)，各次Kruskal排序总O(HMlogM)，查询O(QlogH)，空间O(N+M+H)。H是输出相关参数，不能省略。

易错点

端点相同要结束；相等代价使用确定次关键字，避免重复点。凸包判定用整数，查询用long double；原图允许多条边，不能先按单一属性删边。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int a, b, u, v;
};
struct Point {
    long long u, v;
    bool operator==(const Point &o) const {
        return u == o.u && v == o.v;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, Q;
    cin >> n >> m >> Q;
    vector<Edge> e(m);
    for (auto &x : e) {
        cin >> x.a >> x.b >> x.u >> x.v;
        --x.a;
        --x.b;
    }
    auto mst = [&](long long a, long long b) {
        vector<int> ord(m), p(n), sz(n, 1);
        iota(ord.begin(), ord.end(), 0);
        iota(p.begin(), p.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
            long long x = a * e[i].u + b * e[i].v, y = a * e[j].u + b * e[j].v;
            if (x != y)
                return x < y;
            if (e[i].u != e[j].u)
                return e[i].u < e[j].u;
            return e[i].v < e[j].v;
        });
        function<int(int)> f = [&](int x) {
            while (p[x] != x) {
                p[x] = p[p[x]];
                x = p[x];
            }
            return x;
        };
        Point r{0, 0};
        for (int i : ord) {
            int x = f(e[i].a), y = f(e[i].b);
            if (x != y) {
                if (sz[x] < sz[y])
                    swap(x, y);
                p[y] = x;
                sz[x] += sz[y];
                r.u += e[i].u;
                r.v += e[i].v;
            }
        }
        return r;
    };
    Point A = mst(1, 0), B = mst(0, 1);
    vector<Point> hull(1, A);
    if (!(A == B)) {
        vector<pair<Point, Point>> st(1, {A, B});
        while (!st.empty()) {
            auto z = st.back();
            st.pop_back();
            auto l = z.first, r = z.second;
            long long a = l.v - r.v, b = r.u - l.u;
            Point c = mst(a, b);
            if (a * c.u + b * c.v < a * l.u + b * l.v) {
                st.push_back({c, r});
                st.push_back({l, c});
            } else
                hull.push_back(r);
        }
    }
    while (Q--) {
        long double a, b;
        cin >> a >> b;
        auto val = [&](int i) {
            return a * hull[i].u + b * hull[i].v;
        };
        int l = 0, r = hull.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (val(mid) <= val(mid + 1))
                r = mid;
            else
                l = mid + 1;
        }
        cout << fixed << setprecision(3) << val(l) << '\n';
    }
}