给出
SJX 大爷教我的(
记原图的
对于
对于
自然的,我们想到枚举每一条非树边,并将其所连接的两个节点在
更具体的,记
问题转化为如何维护这个过程。
一个经典的解法是利用树链剖分与线段树,网络上大多数的题解也是如此。不过这样做的复杂度是
我们采用一种码量更少,复杂度更为优秀的
记录倍增数组
令标记
考虑倍增求 LCA 的过程,同样的,我们不断从
最后将标记下传,即
感性理解起来就是将
至此,对于删除树边
(这里我们假设
代码实现上有一些区别。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXM = 1e6 + 10;
const int MAX_LOG = 17;
const int INF = 1e9;
int n, m, mstval, q;
void chkmin(int& a, int b) { if (a > b) a = b; }
namespace G {
int head[MAXN], e_cnt;
int dwn[MAXN << 1];
struct Edge { int nxt, to, id; } e[MAXN << 1];
void add(int u, int v, int id) { e[++e_cnt].nxt = head[u], e[e_cnt].to = v, e[e_cnt].id = id, head[u] = e_cnt; }
struct Vertix { int dep, fa, ff[MAX_LOG + 3], tag[MAX_LOG + 3]; } vtx[MAXN];
void dfs(int u) {
vtx[u].dep = vtx[vtx[u].fa].dep + 1, vtx[u].ff[0] = vtx[u].fa, vtx[u].tag[0] = INF;
for (int i = 1; i <= MAX_LOG; ++i) vtx[u].ff[i] = vtx[vtx[u].ff[i - 1]].ff[i - 1], vtx[u].tag[i] = INF;
for (int _ = head[u], v; _; _ = e[_].nxt) {
v = e[_].to;
if (v == vtx[u].fa) continue;
vtx[v].fa = u, dwn[e[_].id] = v, dfs(v);
}
}
void update(int u, int v, int w) {
if (vtx[u].dep < vtx[v].dep) swap(u, v);
for (int i = MAX_LOG; ~i; --i) if (vtx[u].dep - (1 << i) >= vtx[v].dep) {
chkmin(vtx[u].tag[i], w), u = vtx[u].ff[i];
}
if (u == v) return ;
for (int i = MAX_LOG; ~i; --i) if (vtx[u].ff[i] != vtx[v].ff[i]) {
chkmin(vtx[u].tag[i], w), chkmin(vtx[v].tag[i], w);
u = vtx[u].ff[i], v = vtx[v].ff[i];
}
chkmin(vtx[u].tag[0], w), chkmin(vtx[v].tag[0], w);
}
}
namespace Kruskal {
struct DSU {
int fa[MAXN];
void init() { iota(fa + 1, fa + n + 1, 1); }
int gf(int x) { return x == fa[x] ? x : fa[x] = gf(fa[x]); }
void merge(int x, int y) { if (gf(x) != gf(y)) fa[gf(y)]= gf(x); }
} dsu;
struct Edge { int u, v, w, id; bool operator <(const Edge& _) const { return w < _.w; } } e[MAXN], cpy[MAXN];
int kruskal() {
sort(e + 1, e + m + 1);
dsu.init();
int cnt = 0;
for (int i = 1; i <= m && cnt < n - 1; ++i) {
if (dsu.gf(e[i].u) != dsu.gf(e[i].v)) {
mstval += e[i].w;
dsu.merge(e[i].u, e[i].v), cnt++;
G::add(e[i].u, e[i].v, e[i].id), G::add(e[i].v, e[i].u, e[i].id);
}
}
if (cnt < n - 1) { return -1; }
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1, u, v, w; i <= m; ++i) {
scanf("%d %d %d", &u, &v, &w); Kruskal::e[i] = {u, v, w, i}, Kruskal::cpy[i] = Kruskal::e[i];
}
scanf("%d", &q);
if (Kruskal::kruskal() == -1) { for (int i = 1; i <= q; ++i) puts("Not connected"); return 0; }
G::dfs(1);
for (int i = 1; i <= m; ++i) {
if (!G::dwn[Kruskal::e[i].id]) G::update(Kruskal::e[i].u, Kruskal::e[i].v, Kruskal::e[i].w);
}
for (int i = MAX_LOG; i; --i) {
for (int j = 1; j <= n; ++j) {
chkmin(G::vtx[j].tag[i - 1], G::vtx[j].tag[i]);
chkmin(G::vtx[G::vtx[j].ff[i - 1]].tag[i - 1], G::vtx[j].tag[i]);
}
}
for (int _ = 1; _ <= q; ++_) {
int t; scanf("%d", &t);
if (!G::dwn[t]) printf("%d\n", mstval);
else {
int ans = G::vtx[G::dwn[t]].tag[0];
if (ans == INF) puts("Not connected");
else printf("%d\n", mstval - Kruskal::cpy[t].w + ans);
}
}
return 0;
}
感觉这方法还可以拓展?