1 条题解

  • 0
    @ 2026-11-12 21:06:33

    T3 城市生长(rebuild)题解

    题意简述

    有 nn 个点的无向图,mm 条边按时间 tit_i 依次加入。qq 次询问 (u,k)(u,k):求最早的日期 dd,使得加入所有 ti≤dt_i\le d 的边后,uu 所在连通块大小至少为 kk。不存在输出 −1-1,k=1k=1 时答案为 00。

    思路

    离线加边与并查集

    把所有边按 tit_i 从小到大排序,依次加入,用并查集维护连通块大小。如果对每次询问都重新模拟一遍,复杂度是 O(qm)O(qm),无法通过。

    我们需要一种能快速回答“uu 所在连通块大小第一次达到 kk 的时间”的结构。

    Kruskal 重构树

    在并查集合并两个连通块时,不直接合并,而是新建一个节点:

    • 新节点的两个儿子分别是原来两个连通块的“代表节点”;
    • 新节点的点权为当前边的建成时间 tt;
    • 新节点的子树大小为两个连通块大小之和。

    如果一条边连接的两个点已经在同一个连通块中,就跳过这条边。最终得到一片森林,称为 Kruskal 重构树。原图的 nn 个点是叶子,每次有效合并产生一个内部节点,所以总节点数不超过 2n−12n-1。

    这棵树有以下性质:

    1. 一个节点的子树恰好是某次合并后形成的一个连通块;
    2. 节点的点权是形成这个连通块时最后加入的那条边的时间;
    3. 从叶子 uu 往根走,子树大小严格递增,点权单调不降。

    回答询问

    对于询问 (u,k)(u,k):

    • 若 k=1k=1,答案为 00;
    • 若 uu 所在 Kruskal 树的根节点子树大小都小于 kk,说明 uu 的连通块永远达不到 kk,输出 −1-1;
    • 否则,从叶子 uu 往上找最后一个子树大小小于 kk 的祖先 vv。那么 vv 的父亲就是第一个子树大小 ≥k\ge k 的祖先,它的点权就是答案。

    “最后一个满足条件的祖先”可以用倍增在 O(log⁡n)O(\log n) 时间内找到:从高位到低位尝试跳,若跳到的祖先子树大小仍小于 kk,就跳过去。

    正确性证明

    引理 1: 对任意节点 xx,xx 的子树恰好是某个时刻的一个连通块。

    对合并次数归纳。叶子是初始的单个点连通块。每次新建节点时,它的两个儿子分别是当前两个连通块的代表,子树并起来就是合并后的连通块。

    引理 2: 从叶子 uu 到根的路径上,子树大小严格递增,点权单调不降。

    每次合并至少把两个非空连通块合并,所以大小严格增加。边按时间排序后处理,后创建的节点点权不小于先创建的节点点权。

    引理 3: 设 vv 是 uu 到根路径上第一个子树大小 ≥k\ge k 的节点,则 weight(v)weight(v) 是 uu 的连通块第一次达到大小 kk 的日期。

    在 weight(v)weight(v) 这一天,vv 所代表的连通块已经形成,且大小 ≥k\ge k。而在 weight(v)weight(v) 之前,uu 所在的连通块是 vv 的某个后代(或 uu 自己),其大小都小于 kk。因此第一次达到 kk 的日期就是 weight(v)weight(v)。

    定理: 算法输出正确。

    若根的大小都小于 kk,则任何时刻 uu 的连通块都达不到 kk,输出 −1-1 正确。否则由引理 3,倍增找到的第一个大小 ≥k\ge k 的祖先的点权就是答案。k=1k=1 时不需要加边,答案为 00。

    复杂度

    排序 O(mlog⁡m)O(m\log m);并查集 O((n+m)α(n))O((n+m)\alpha(n));倍增预处理 O(nlog⁡n)O(n\log n);每次询问 O(log⁡n)O(\log n)。

    总时间复杂度 O(mlog⁡m+(n+q)log⁡n)O(m\log m+(n+q)\log n),空间复杂度 O(nlog⁡n+m)O(n\log n+m)。

    参考代码(C++)

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    struct Edge {
        int t, u, v;
        bool operator<(const Edge &o) const { return t < o.t; }
    };
    
    int main() {
        freopen("rebuild.in", "r", stdin);
        freopen("rebuild.out", "w", stdout);
    
        int n, m, q;
        if (scanf("%d %d %d", &n, &m, &q) != 3) return 0;
    
        vector<Edge> edges(m);
        for (int i = 0; i < m; i++)
            scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].t);
        sort(edges.begin(), edges.end());
    
        int maxNodes = 2 * n + 5;
        vector<int> dsu(maxNodes), sz(maxNodes), par(maxNodes, 0), weight(maxNodes, 0);
        for (int i = 1; i <= n; i++) {
            dsu[i] = i;
            sz[i] = 1;
            weight[i] = 0;
        }
    
        auto find = [&](int x) {
            int r = x;
            while (dsu[r] != r) r = dsu[r];
            while (dsu[x] != x) {
                int y = dsu[x];
                dsu[x] = r;
                x = y;
            }
            return r;
        };
    
        int tot = n;
        for (const Edge &e : edges) {
            int ru = find(e.u), rv = find(e.v);
            if (ru == rv) continue;
            ++tot;
            dsu[ru] = dsu[rv] = tot;
            dsu[tot] = tot;
            par[ru] = par[rv] = tot;
            weight[tot] = e.t;
            sz[tot] = sz[ru] + sz[rv];
        }
    
        int LOG = 1;
        while ((1 << LOG) <= tot) LOG++;
        vector<vector<int>> up(LOG, vector<int>(tot + 1, 0));
        for (int v = 1; v <= tot; v++) up[0][v] = par[v];
        for (int j = 1; j < LOG; j++)
            for (int v = 1; v <= tot; v++)
                up[j][v] = up[j - 1][up[j - 1][v]];
    
        while (q--) {
            int u, k;
            scanf("%d %d", &u, &k);
            if (k <= 1) {
                puts("0");
                continue;
            }
            int root = find(u);
            if (sz[root] < k) {
                puts("-1");
                continue;
            }
            int v = u;
            for (int j = LOG - 1; j >= 0; j--) {
                int a = up[j][v];
                if (a != 0 && sz[a] < k) v = a;
            }
            printf("%d\n", weight[par[v]]);
        }
        return 0;
    }
    

    易错点

    1. k=1k=1 要特判输出 00:此时不需要任何道路,不能去重构树上找祖先。
    2. 询问只与 uu 有关:题目不是问 uu 和 vv 何时连通,而是问 uu 所在连通块何时达到大小 kk,不要读错题意。
    3. 重边与相同时间:连接同一连通块内部的边直接跳过;相同时间的多条边可以任意顺序处理,答案的日期不变。
    4. 重构树可能是一条深度为 nn 的链:例如路径图按 1−2,2−3,…1-2,2-3,\dots 的顺序加边。不能递归 DFS,也不能暴力爬父亲,要用倍增。
    5. 数组要开到 2n2n:每次有效合并新建一个节点,总节点数最多 2n−12n-1。
    6. 并查集根与重构树根:代码中 find(u) 返回的是最终连通块的 DSU 根,也是重构树的根;par 数组才是重构树的父亲指针,两者不要混用。
    7. m=0m=0:此时所有点都是孤立的,k>1k>1 的询问全部输出 −1-1。

    测试点设计

    测试点 设计意图
    1 样例 1,基本加边与询问
    2 样例 2,两个互不连通的连通块,检验 −1-1
    3 n=2,m=0n=2,m=0,检验 k=1k=1 与无解
    4 n=105,m=0n=10^5,m=0,大量 k=1k=1 与 −1-1 询问
    5 n=1000n=1000 的链,边权递增,检验连通块向两侧生长
    6 n=1000n=1000 的链,所有边同一天建成,检验相同时间处理
    7 随机图 n=2000,m=5000n=2000,m=5000,随机时间与询问
    8 随机图 n=2×105,m=4×105n=2\times 10^5,m=4\times 10^5,大量连通块与随机询问
    9 随机树 n=2×105n=2\times 10^5,边权为随机排列
    10 路径图 n=2×105n=2\times 10^5,边权递增,重构树退化为深链,检验倍增
    11 两个互不连通的大连通块,大量跨块询问输出 −1-1
    12 连通图 n=2×105,m=4×105n=2\times 10^5,m=4\times 10^5,所有边同一天建成,答案只有 00 和该日期
    • 1

    信息

    ID
    8
    时间
    2000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    2
    已通过
    2
    上传者