Daleks' Invasion 题解

Daleks' Invasion

题目大意

给定一张无向带权图，对于每条边求一个最大的 \(x\)，使得将这条边的边权修改为 \(x\) 后这条边能位于这张图的最小生成树上。

思路分析

没事干了就把之前写过的题拉出来水题解。

我们先把原图的最小生成树求出来，考虑每条边 \((u,v)\)，分类讨论：

• 如果这条边不在原图最小生成树上：

容易发现，这时这条边的 \(x\) 就是在最小生成树上 \(u\) 到 \(v\) 的最大边权 \(w\)。用一个随便什么东西维护就行了。（倍增，树剖套 ST 表，树剖套线段树……能用的东西太多了）

证明是容易的：

首先考虑可行性，当我们将这条边的边权修改为 \(w\) 后，我们显然可以通过断掉之前最大边权所在的边，再加入这条边的方式生成一个新的合法最小生成树。

再考虑极大性，这就更显然了，由于最小生成树是一颗瓶颈生成树，也就是说最小生成树保证最大边权最小。那么如果 \(x=w+1\)，并且这条边还在最小生成树上的话，那么就与最小生成树的性质矛盾了，因此极大性成立。

• 如果这条边在原图的最小生成树上：

类似的，我们可以发现这条边的 \(x\) 是在原图中 \(u\) 到 \(v\) 的所有不经过树边的简单路径中的最小边权 \(w\)。

证明也类似上文的证明，此处略去。读者自证不难。

实现方式也很多，可以先枚举所有不在最小生成树上的边 \((u,v,w)\)，用树剖套线段树支持 \(u\) 到 \(v\) 的链对 \(w\) 取 \(\min\)。

也可以先排个序然后将区间取 \(\min\) 改为区间赋值，但其实没什么区别。

那么这题就做完了，总时间复杂度为 \(O(m\log ^2n)\)。

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;
const int N = 1001000;
#define inf 1000000000
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)

int n, m, in1, in2, in3, cnt;
int fa[N], siz[N], son[N], dep[N], top[N], dfn[N], rnk[N];
int vis[N], fat[N], pw[N], ans[N], inp[N];

int find(int x){
    return fat[x] == x ? x : fat[x] = find(fat[x]);
}

struct Edge{
    int u, v, w, id;
}e[N];

vector <pair<int, int>> to[N];

void dfs_1(int s, int gr){
    dep[s] = dep[gr] + 1;
    siz[s] = 1; fa[s] = gr;
    for (auto [v, w] : to[s]) {
        if (v == gr) continue;
        dfs_1(v, s);
        siz[s] += siz[v];
        pw[v] = w;
        if (siz[son[s]] < siz[v]) son[s] = v;
    }
}

void dfs_2(int s, int tp){
    top[s] = tp; dfn[s] = ++ cnt; rnk[cnt] = s;
    if (!son[s]) return ;
    dfs_2(son[s], tp);
    for (auto [v, w] : to[s]) 
        if (v != fa[s] && v != son[s]) dfs_2(v, v);
}

struct STn{
    int maxn;
    int tag;
};
struct ST{
    STn a[N << 2];
    void build(int p, int l, int r){
        a[p].tag = inf;
        if (l == r) return a[p].maxn = inp[l], void();
        build(ls, l, mid); build(rs, mid + 1, r);
        a[p].maxn = max(a[ls].maxn, a[rs].maxn);
    }
    void min_t(int p, int k){
        a[p].maxn = min(a[p].maxn, k);
        a[p].tag = min(a[p].tag, k);
    }
    void push_down(int p){
        if (a[p].tag == inf) return ;
        min_t(ls, a[p].tag); min_t(rs, a[p].tag);
        a[p].tag = inf;
    }
    void change(int p, int l, int r, int x, int y, int k){
        if (x <= l && r <= y) return min_t(p, k);
        push_down(p);
        if (x <= mid) change(ls, l, mid, x, y, k);
        if (y > mid) change(rs, mid + 1, r, x, y, k);
        a[p].maxn = max(a[ls].maxn, a[rs].maxn);
    }
    int ask(int p, int l, int r, int x, int y){
        if (x <= l && r <= y) return a[p].maxn;
        push_down(p);
        if (y <= mid) return ask(ls, l, mid, x, y);
        if (x > mid) return ask(rs, mid + 1, r, x, y);
        return max(ask(ls, l, mid, x, y), ask(rs, mid + 1, r, x, y));
    }
}tree;

int ask(int x, int y){
    int res = -inf;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res = max(res, tree.ask(1, 1, n, dfn[top[x]], dfn[x]));
        x = fa[top[x]]; 
    }
    if (x != y) res = max(res, tree.ask(1, 1, n, min(dfn[x], dfn[y]) + 1, max(dfn[x], dfn[y])));
    return res;
}

void change(int x, int y, int k){
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        tree.change(1, 1, n, dfn[top[x]], dfn[x], k);
        x = fa[top[x]];
    }
    if (x != y) tree.change(1, 1, n, min(dfn[x], dfn[y]) + 1, max(dfn[x], dfn[y]), k);
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++) fat[i] = i;
    for (int i = 1; i <= m; i ++) {
        scanf("%d %d %d", &in1, &in2, &in3);
        e[i] = Edge{in1, in2, in3, i};
    }
    sort(e + 1, e + m + 1, [](Edge a, Edge b){return a.w < b.w;});
    for (int i = 1; i <= m; i ++)
        if (find(e[i].u) != find(e[i].v)) {
            to[e[i].u].push_back({e[i].v, e[i].w});
            to[e[i].v].push_back({e[i].u, e[i].w});
            vis[e[i].id] = 1;
            fat[find(e[i].u)] = find(e[i].v);
        }
    dfs_1(1, 0); dfs_2(1, 1);
    for (int i = 1; i <= n; i ++) inp[dfn[i]] = pw[i];
    tree.build(1, 1, n);
    for (int i = 1; i <= m; i ++)
        if (!vis[e[i].id]) ans[e[i].id] = ask(e[i].u, e[i].v);
    for (int i = 1; i <= n; i ++) inp[i] = inf;
    tree.build(1, 1, n);
    for (int i = 1; i <= m; i ++)
        if (!vis[e[i].id]) change(e[i].u, e[i].v, e[i].w);
    for (int i = 1; i <= m; i ++) 
        if (vis[e[i].id]) {
            int u = e[i].u, v = e[i].v;
            if (dep[u] < dep[v]) swap(u, v);
            ans[e[i].id] = tree.ask(1, 1, n, dfn[u], dfn[u]);
        }
    for (int i = 1; i <= m; i ++) cout << ans[i] << '\n';
    return 0;
}