题解：CF1633E Spanning Tree Queries

AKCoder · 2026-07-02 22:09:54 · 题解

前置知识：小学二年级的函数，MST。

建议使用 desmos 配套学习。

我们发现，两个图像的交点在他们的中点。

首先，MST 使用 Kruskal 求的时候只跟大小关系有关。

所以，当大小关系改变时，当且仅当跨过了中点。

所以，能改变 MST 关系的询问只有 m^2 个。

每一次跑一遍 MST，总的复杂度是 O(m^3\log_2m)。

但这样还是过不去。

询问时如果没有在交点上的不久炸了吗？

所以，我们要考虑偏移量。

因为从交点出发，一定是一个一次函数。

设偏移量为 \Delta，交点为 m，则询问点变成了 m + \Delta，我们就设 x 就为 m + \Delta。

设左侧单调递减的部分的个数为 s，则右侧为 n - 1 - s，有 n - 1 条边。

对于某一条被选中的边，权值为 w。

如果 w \le m（共有 s 条）：

原来的距离为：

现在变成了：

因为有 s 个 \Delta，所以就为 s \cdot \Delta。

若 w > m（共有 n - s - 1 条）：

原来距离为：

现在变成了：

因为有 n - s - 1 个，所以就为 s \cdot -\Delta。

然后就做完了。

坑点：要将所有的 w，\lfloor \dfrac{w}{2} \rfloor，\lceil \dfrac{w}{2} \rceil 加入 Kruskal 中，不然会 WA test 6。

代码解析：

void init() {  
    vid.push_back(0); // 要添加 0，0 表示正常 MST
    for (auto [w, u, v] : vec) vid.push_back(w); // 加入 w 这条边
    for (int i = 0; i < m; i++) {  
        for (int j = i + 1; j < m; j++) {  
            int v0 = vec[i][0], v1 = vec[j][0];  
            vid.push_back((v0 + v1) / 2); // 加入 floor(w / 2) 这条边
            vid.push_back((v0 + v1 + 1) / 2); // 加入 ceil(w / 2) 这条边
        }  
    }  
    sort(all(vid)); // 排序并去重
    vid.erase(unique(all(vid)), vid.end());  
    for (auto i : vid) kruskal(i); // 跑 Kruskal  
}

void kruskal(int mid) {  
    // 正常 Kruakal，然后注意排序的问题，我们肯定想让 bug 经可能大
    vector<array<int, 3>> v = vec;  
    for (int i = 1; i <= n; i++) fa[i] = i;  
    sort(all(v), [&](const ARR &A, const ARR &B) { // 注意排序
        if (abs(A[0] - mid) != abs(B[0] - mid))  
            return abs(A[0] - mid) < abs(B[0] - mid);  
        return A[0] > B[0];  
    });  
    ll ans = 0, bug = 0;  
    for (auto [w, x, y] : v) {  
        int w1 = abs(w - mid);  
        if (unite(x, y)) {  
            if (w <= mid) ++bug;  // 记录 <= mid 的个数
            ans += w1;  
        }  
    }  
    vans.push_back(make_pair(ans, bug)); // 增加答案
}

int main() {  
    scanf("%d%d", &n, &m);  
    for (int i = 1; i <= m; i++) {  
        int u, v, w;  
        scanf("%d%d%d", &u, &v, &w);  
        vec.push_back({w, u, v});  
    }  
    init(); // 预处理
    scanf("%d%d%d%d%d", &p, &k, &a, &b, &c);  
    auto calc = [&](ll x) -> ll {  
        auto idv = upper_bound(all(vid), x); // 找到第一个大于他的，然后 -1 表示第一个小于等于他的
        int id = idv - vid.begin() - 1;  
        auto [ans, siz] = vans[id];  
        ll deltaq = x - vid[id];  
        return ans + deltaq * siz - deltaq * (n - 1 - siz);  
    };  
    ll q = 0;  
    ll xans = 0;  
    for (auto &j : vid) debug(j);  
    for (auto &i : vans) debug(i);  
    for (int i = 1; i <= p; i++) {  
        scanf("%lld", &q);  
        xans ^= calc(q);  
        debug(calc(q));  
    }  
    debug("");  
    for (int i = p + 1; i <= k; i++) {  
        q = ((ll)q * a + b) % c, xans ^= calc(q);  
        debug(calc(q));  
    }  
    printf("%lld\n", xans);  
    return 0;  
}

PS：debug 表示调试信息。

笑点分析：调试了 inf 世纪。