题解：P13783 [eJOI 2022] Bounded Spanning Tree

yuyang0974 · 2025-12-18 17:07:57 · 题解

~模拟赛没调出来的贪心构造题。~

题目简介

你需要给每条边分**互不相同**的整数编号，值域为 $\left[ 1, m \right]$。求一种构造方案，满足前 $n - 1$ 条边构成的树是图的最小生成树。 ## 思路历程 ### $m = n - 1

这显然是一棵树（题目保证了前 n - 1 条边构成树）。

那对于树，其最小生成树一定唯一（~废话~）。

所以就只需要满足每一条边的限制即可。

这有一种贪心策略，我们考虑从小到大分配编号，那么分配到编号 i 时，我们总是让 l_j \le i 的所有 j 中最小的 r_j 先得到这个编号。

:::info[贪心的证明] 嘿嘿。

当 r_i < r_j 时，不妨设当枚举到 x 选了 i，枚举到 y 选了 j，无非有一下两种情况：

情况一：

我们交换 i,j 选择顺序，发现并无大碍。但是这不优，所以多此一举。

情况二：

这种情况你一换反而更劣了。

综上，~你别换~你按照这样的贪心总是最优的。 :::

所以，你就这样贪心跑，如果贪心过程中没有边满足条件了（也就是没有边可以被当前枚举到的 x 赋值了），那就无解。

m > n - 1

这显然不是一棵树。

我们遇到含有其他边的情况，一般是：先建出树，然后观察非树边的限制是什么。

我们给出方案：

对于每一条非树边，l 应当改为被其包含的所有树边中的 l_{\max} + 1。
对于每一条树边，r 应当改为包含其的所有非树边中的 r_{\min} - 1。

:::info[方案咋出来的？]

所以我们先把前 n - 1 条边建出树来，然后对其中一个“非树边——树边”系统进行观察。

看看这个美丽的树（蓝色是非树边，红色是被“包含”的树边）。

首先，如果这棵树要满足是最小生成树，那么这些红边必须都小于蓝边，蓝边必须大于这些红边。

否则，就像下面这样：

我们完全可以用这条蓝边代替其中一条红边。

你可能会想：那我们能不能直接复用上面的结论？

当然不能，这就是反例：

输入格式：

本身应该是有解的，例如这一组：

1 2 4 3 5

但是！只根据上面的贪心，你会发现：你先取 1 之后，会立马取 3！这显然会形成无解（因为蓝边只能在被自己“包围”的红边全都选完后才可以选，这样才满足原树是最小生成树）。

~如何呢？~ 我们该怎么办？

我们考虑，这个无解的原因是什么？是不是这个 2 号边有问题？

它明明不可以取到 r = 5 的值（不然蓝边一定小于它，也就不满足最小生成树）！

所以，我们是不是应当对于每一条红边，把他们的 r 都削弱一下，不让他们超出蓝边的限制？

同样的，对于每条蓝边，是不是也不可以取到 l 小于红边的 l 的情况？

那我们就也拿这些红边，限制一下蓝边即可。

那限制完之后，蓝边与一条它的红边是不是一定是这样的结构？

也就是，他们的左、右端点都有严格的偏序关系。

那这样处理完后，是不是我们再这样正常做 m = n - 1 部分的贪心，就正确了？

这是因为，我们想选蓝区间，在贪心的策略下，必然先选完所有红区间。

所以，这样转化是成立的。 :::

有了方案，那我们就按照 m = n - 1 里面的东西，正常做即可。

具体维护方法，可以使用倍增来修改，这样是 O(\sum (m \log{n})) 的复杂度，可以接受。

:::info[如何倍增？] 首先，我们要边权转点权，就是把树边的归属权给深度较大的那个点。这样是为了方便我们处理。

我们先考虑如何更新非树边。

普通的倍增处理了你跳到 2 的幂次级别的祖先。

那你不妨再开一个 g_{u,k} 表示跳到了 2^k 级祖先的路径信息。这个可以和倍增的 dfs 一起预处理。然后对于每个非树边，我们路径查询即可，这个也可以用倍增实现。

我们再考虑如何更新树边。

我们可以枚举每条非树边，像路径查询那样更新路径信息。然后类似线段树的 pushdown，枚举每个状态并下放即可。查询可以直接查询 g_{u,0}，也就是自己代表的那条边。 :::

AC 代码

:::success[AC 代码]

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

#define tp template<typename T>
#define tpp template<typename T, typename ...T1>
#define tpvoid tp void
#define tppvoid tpp void
#define bug(x) {cout << #x":" << x << "   ";}
#define _n {putchar('\n');}
#define _b {putchar(' ');}
#define _t(x) {cout << x;}

tpvoid read(T &x) {
    x = 0;
    char c = getchar(), f = 'a';
    while(c < '0' || c > '9') {
        if(!(c ^ '-')) f = 'b';
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ '0');
        c = getchar();
    }
    if(f ^ 'a') x = -x;
}
tppvoid read(T &x, T1 &...x1) {read(x); read(x1...);}

int n, m;
const int maxn = 5e5 + 5;
const int maxm = 5e5 + 5;

#define WA {printf("NO\n"); return;}

struct Line {
    int u, v, l, r;
    bool intree;
    Line(int _u = 0, int _v = 0, int _l = 0, int _r = 0, bool _in = false) :
        u(_u), v(_v), l(_l), r(_r), intree(_in) {}
    void In(bool in) {
        read(u, v, l, r);
        intree = in;
    }
} line[maxm];

struct Edge {
    int nex, v, id;
    Edge(int _nex = -1, int _v = 0, int _id = 0) : nex(_nex), v(_v), id(_id) {}
} edge[maxn << 1];
int head[maxn], cnt;
void init() {
    cnt = 0;
    for(int i = 1; i <= n; i ++) head[i] = -1;
}
void add(int u, int v, int id) {
    edge[cnt] = Edge(head[u], v, id);
    head[u] = cnt ++;
}
void Add(int u, int v, int id) {
    add(u, v, id);
    add(v, u, id);
}

int from[maxn];

int deep[maxn], f[maxn][22], g[maxn][22];
void dfs(int u, int fa, int id) {
    deep[u] = deep[fa] + 1;
    f[u][0] = fa;
    g[u][0] = line[id].l + 1;
    from[u] = id;
    int lg = __lg(deep[u]);
    for(int i = 1; i <= lg; i ++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
        g[u][i] = max(g[u][i - 1], g[f[u][i - 1]][i - 1]);
    }
    for(int i = head[u], v; ~i; i = edge[i].nex) {
        v = edge[i].v;
        if(!(v ^ fa)) continue;
        dfs(v, u, edge[i].id);
    }
}

int query_line(int u, int v) {
    int ans = 0;
    if(deep[u] < deep[v]) swap(u, v);
    int tmp = deep[u] - deep[v];
    if(tmp) for(int i = __lg(tmp); ~i; i --) if((tmp >> i) & 1) ans = max(ans, g[u][i]), u = f[u][i];
    if(!(u ^ v)) return ans;
    for(int i = __lg(deep[u]); ~i; i --) {
        if(f[u][i] ^ f[v][i]) {
            ans = max(ans, max(g[u][i], g[v][i]));
            u = f[u][i];
            v = f[v][i];
        }
    }
    ans = max(ans, max(g[u][0], g[v][0]));
    return ans;
}
void update_line(int u, int v, int val) {
    if(deep[u] < deep[v]) swap(u, v);
    int tmp = deep[u] - deep[v];
    if(tmp) for(int i = __lg(tmp); ~i; i --) if((tmp >> i) & 1) g[u][i] = min(g[u][i], val), u = f[u][i];
    if(!(u ^ v)) return;
    for(int i = __lg(deep[u]); ~i; i --) {
        if(f[u][i] ^ f[v][i]) {
            g[u][i] = min(g[u][i], val);
            g[v][i] = min(g[v][i], val);
            u = f[u][i];
            v = f[v][i];
        }
    }
    g[u][0] = min(g[u][0], val);
    g[v][0] = min(g[v][0], val);
}

vector<int> vt[maxm];

struct node {
    int id, r;
    node(int _id = 0, int _r = 0) : id(_id), r(_r) {}
    friend bool operator < (node e1, node e2) {
        if(e1.r ^ e2.r) return e1.r < e2.r;
        else if(line[e1.id].intree) {
            if(line[e2.id].intree) return e1.id < e2.id;
            return true;
        }
        else {
            if(line[e2.id].intree) return false;
            return e1.id < e2.id;
        }
    }
    friend bool operator == (node e1, node e2) {
        return e1.r == e2.r && (e1.id == e2.id);
    }
};
set<node> st;
set<node> :: iterator it;

int ans[maxm];
void Solve() {
    read(n, m);
    for(int i = 1; i <= m; i ++) line[i].In(i < n);
    init();
    for(int i = 1; i < n; i ++) Add(line[i].u, line[i].v, i);
    for(int i = __lg(n); ~i; i --) for(int j = 0; j <= n; j ++) f[j][i] = g[j][i] = 0;
    dfs(1, 0, 0);
    for(int i = n; i <= m; i ++) {
        line[i].l = max(line[i].l, query_line(line[i].u, line[i].v));
        if(line[i].l > line[i].r) WA;
    }
    for(int i = __lg(n); ~i; i --) for(int j = 1; j <= n; j ++) g[j][i] = m;
    for(int i = n; i <= m; i ++) update_line(line[i].u, line[i].v, line[i].r - 1);
    for(int k = __lg(n); k; k --) for(int u = 2; u <= n; u ++) if(g[u][k]) g[u][k - 1] = min(g[u][k - 1], g[u][k]), g[f[u][k - 1]][k - 1] = min(g[f[u][k - 1]][k - 1], g[u][k]);
    for(int i = 2, id; i <= n; i ++) {
        id = from[i];
        //bug(id);
        line[id].r = min(line[id].r, g[i][0]);
        //bug(g[i][0]);
        if(line[id].l > line[id].r) WA;
    }
    st.clear();
    for(int i = 1; i <= m; i ++) vt[i].clear();
    for(int i = 1, l, r; i <= m; i ++) {
        l = line[i].l, r = line[i].r;
        vt[l].push_back(i);/*
        bug(i);
        bug(l);
        bug(r);
        _n;*/
    }
    node tmp;
    for(int i = 1; i <= m; i ++) {
        for(int id : vt[i]) st.insert( node( id, line[id].r ) );
        if(st.empty()) WA;
        it = st.begin();
        tmp = *it;
        st.erase(it);
        if(tmp.r < i) WA;
        ans[tmp.id] = i;
    }
    printf("YES\n");
    for(int i = 1; i <= m; i ++) printf("%d%c", ans[i], i ^ m ? ' ' : '\n');
}

int main() {
    //freopen("chesed.in", "r", stdin);
    //freopen("chesed.out", "w", stdout);
    int t;
    read(t);
    while(t --) Solve();
    return 0;
}

:::