题目大意
给定一张无向带权图，对于每条边求一个最大的 \(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;
}