被一道题创了三天
我们先考虑如何求给定两点在原图的最短路。套路地，建出 Kruskal 重构树，最短路就是两点 \(\text{LCA}\) 的权值。
对于在补图的最短路，我们希望如法炮制，建出补图的 Kruskal 重构树。但是由于边数太多无法跑 Kruskal。不妨退一步，建出补图的最小生成树，那么两点的最短路就是这两点在最小生成树上的最大边权。
求一个稠密图的最小生成树，可以考虑 Boruvka 算法。其思想基于每个点的最短邻边一定在最小生成树上，流程是每轮对每个连通块找到一条连向另一连通块的最短边，然后合并两端点。因为每轮连通块数量至少减半，所以一共会进行 \(O(\log n)\) 轮。
于是现在我们考虑对每个点 \(u\)，求出它连出去的最小出边，并且边的另一端点不和 \(u\) 在同一连通块。我们不妨倍增找到 \(u\) 在 Kruskal 重构树上的最浅祖先，使得它包含的所有叶子不是都和 \(u\) 在同一连通块。
考虑把 Kruskal 重构树拍平到序列上，那么每个点的子树管辖 dfn 序在 \([l_i, r_i]\) 中的叶子。设 \(f_i\) 为 \(i\) 所在连通块的代表元，\(g_i\) 为 dfn 序为 \(i\) 的点，\(d_i\) 为最大的 \(j\) 使得 \(\forall k \in [j, i], f_{g_k} = f_{g_i}\)，也就是说 \(g_{d_i - 1}\) 是 \(i\) 在 dfn 序上往左第一个与 \(g_i\) 不在同一连通块的点。
考虑倍增到 \(u\) 的一个祖先 \(v\) 后，如何判定 \(v\) 子树管辖的叶子不是都和 \(u\) 在同一连通块，并且如果这个条件满足，还要找到这样的一个叶子。如果 \(g_{r_v}\) 不和 \(u\) 在同一连通块，那么 \(g_{r_v}\) 即为所求。否则，dfn 序在 \([d_{r_v}, r_v]\) 中的叶子都和 \(u\) 在同一连通块，若 \(d_{r_v} > l_v\)，那么 \(g_{d_{r_v} - 1}\) 即为所求，否则 \(v\) 不满足条件。
但是有个问题，因为我们求的是补图的最小生成树，所以找到的边不能是原图上有的边。考虑判定 \(v\) 是否满足条件时，对于所有 \(u\) 在原图上连出去的边 \((u, w)\)，\(l_w\) 把 \([l_v, r_v]\) 分成了 \(O(deg_u)\) 个小区间。因为 \(O(\sum deg_u) = O(m)\)，所以我们可以暴力找到 \(O(deg_u)\) 个小区间，再按照上面的方法判定即可。
时间复杂度 \(O(m (\log^2 n + \log m))\)。
code
// Problem: E. Air Reform
// Contest: Codeforces - Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics)
// URL: https://codeforces.com/problemset/problem/1648/E
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
namespace IO {
char ibuf[(1 << 20) + 1], *iS, *iT, obuf[(1 << 20) + 1], *oS = obuf;
#define writesp(x) write(x), pc(' ')
#define writeln(x) write(x), pc('\n')
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
inline int read() {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void flush () {
fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
}
inline void pc (char ch) {
if (oS == obuf + (1 << 20) + 1) flush();
*oS++ = ch;
}
template<typename _Tp>
inline void write (_Tp x) {
static char stk[64], *tp = stk;
if (x < 0) x = ~(x - 1), pc('-');
do *tp++ = x % 10, x /= 10;
while (x);
while (tp != stk) pc((*--tp) | 48);
}
}
using IO::read;
using IO::write;
using IO::pc;
using IO::flush;
const int maxn = 400100;
const int logn = 21;
int n, m, times, ff[maxn], a[maxn], f[maxn][logn], d[maxn];
int st[maxn], ed[maxn], rnk[maxn], dep[maxn], sz[maxn], ans[maxn];
pii c[maxn];
vector<int> G[maxn], gg[maxn];
vector<pii> T[maxn];
struct edg {
int u, v, d, id;
edg(int a = 0, int b = 0, int c = 0, int e = 0) : u(a), v(b), d(c), id(e) {}
} E[maxn];
int find(int x) {
return ff[x] == x ? x : ff[x] = find(ff[x]);
}
inline bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
ff[x] = y;
return 1;
} else {
return 0;
}
}
void dfs(int u) {
if (u <= n) {
st[u] = ++times;
rnk[times] = u;
} else {
st[u] = times + 1;
}
for (int v : G[u]) {
f[v][0] = u;
dep[v] = dep[u] + 1;
dfs(v);
}
ed[u] = times;
}
int fa[maxn], son[maxn], top[maxn], dfn[maxn], b[maxn];
int dfs2(int u, int f, int d) {
fa[u] = f;
sz[u] = 1;
dep[u] = d;
int mx = -1;
for (pii p : T[u]) {
int v = p.fst, k = p.scd;
if (v == f) {
continue;
}
b[v] = k;
sz[u] += dfs2(v, u, d + 1);
if (sz[v] > mx) {
son[u] = v;
mx = sz[v];
}
}
return sz[u];
}
void dfs3(int u, int tp) {
top[u] = tp;
dfn[u] = ++times;
if (!son[u]) {
return;
}
dfs3(son[u], tp);
for (pii p : T[u]) {
int v = p.fst;
if (!dfn[v]) {
dfs3(v, v);
}
}
}
int g[maxn][logn];
inline int qmax(int l, int r) {
if (l > r) {
return 0;
}
int k = __lg(r - l + 1);
return max(g[l][k], g[r - (1 << k) + 1][k]);
}
inline int trqmax(int x, int y) {
int res = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
res = max(res, qmax(dfn[top[x]], dfn[x]));
x = fa[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
res = max(res, qmax(dfn[x] + 1, dfn[y]));
return res;
}
inline int query(int x, int u) {
int lst = st[x] - 1;
for (int v : gg[u]) {
if (st[x] <= st[v] && st[v] <= ed[x]) {
int l = lst + 1, r = st[v] - 1;
if (l <= r) {
if (find(rnk[r]) != find(u)) {
return rnk[r];
} else if (d[r] > l) {
return rnk[d[r] - 1];
}
}
lst = st[v];
}
}
if (lst + 1 <= ed[x]) {
int l = lst + 1, r = ed[x];
if (l <= r) {
if (find(rnk[r]) != find(u)) {
return rnk[r];
} else if (d[r] > l) {
return rnk[d[r] - 1];
}
}
}
return -1;
}
void solve() {
n = read();
m = read();
for (int i = 1; i <= n * 2; ++i) {
vector<int>().swap(G[i]);
vector<int>().swap(gg[i]);
vector<pii>().swap(T[i]);
}
for (int i = 1; i <= m; ++i) {
E[i].u = read();
E[i].v = read();
E[i].d = read();
E[i].id = i;
gg[E[i].u].pb(E[i].v);
gg[E[i].v].pb(E[i].u);
}
sort(E + 1, E + m + 1, [&](const edg &a, const edg &b) {
return a.d < b.d;
});
for (int i = 1; i <= n * 2; ++i) {
ff[i] = i;
}
int ntot = n;
for (int i = 1; i <= m; ++i) {
int u = E[i].u, v = E[i].v, d = E[i].d;
int x = find(u), y = find(v);
if (x != y) {
int z = ++ntot;
ff[x] = ff[y] = z;
a[z] = d;
G[z].pb(x);
G[z].pb(y);
}
}
int rt = ntot;
dep[rt] = 1;
f[rt][0] = 0;
times = 0;
dfs(rt);
for (int i = 1; i <= n; ++i) {
ff[i] = i;
}
for (int j = 1; j <= 19; ++j) {
for (int i = 1; i <= n * 2 - 1; ++i) {
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
sort(gg[i].begin(), gg[i].end(), [&](const int &x, const int &y) {
return st[x] < st[y];
});
}
while (1) {
int cnt = 0;
for (int i = 1; i <= n; ++i) {
cnt += (ff[i] == i);
}
if (cnt == 1) {
break;
}
for (int i = 1; i <= n; ++i) {
c[i] = mkp(2e9, -1);
}
for (int i = 1, j = 1; i <= n; i = (++j)) {
while (j < n && find(rnk[j + 1]) == find(rnk[i])) {
++j;
}
for (int k = i; k <= j; ++k) {
d[k] = i;
}
}
for (int u = 1; u <= n; ++u) {
int x = u;
for (int i = 19; ~i; --i) {
if (!f[x][i]) {
continue;
}
int v = f[x][i];
if (query(v, u) == -1) {
x = v;
}
}
x = f[x][0];
if (x) {
int t = query(x, u);
c[find(u)] = min(c[find(u)], make_pair(a[x], t));
}
}
for (int i = 1; i <= n; ++i) {
if (ff[i] == i) {
if (merge(i, c[i].scd)) {
T[i].pb(c[i].scd, c[i].fst);
T[c[i].scd].pb(i, c[i].fst);
}
}
}
}
times = 0;
for (int i = 1; i <= n; ++i) {
fa[i] = sz[i] = son[i] = dep[i] = top[i] = dfn[i] = 0;
}
dfs2(1, -1, 1);
dfs3(1, 1);
for (int i = 2; i <= n; ++i) {
g[dfn[i]][0] = b[i];
}
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
g[i][j] = max(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 1; i <= m; ++i) {
int u = E[i].u, v = E[i].v;
ans[E[i].id] = trqmax(u, v);
}
for (int i = 1; i <= m; ++i) {
write(ans[i]);
pc(' ');
}
pc('\n');
}
int main() {
int T = read();
while (T--) {
solve();
}
flush();
return 0;
}