题目
分析
倍增神题……（感谢T*C神犇给我讲qwq）
这道题需要考虑最小生成树的性质。首先随便求出一棵最小生成树，把树边和非树边分开处理。
首先，对于非树边\((u,v)\)（表示一条两端点为\(u\)和\(v\)的边，下同）。考虑Kruskal算法的过程，它必定成为树边的充要条件是它的权值小于树上\(u\)到\(v\)之间的路径上的某条边\(e\)，这样就会选中这条边来连接\(u\)和\(v\)所在的连通块而不是选中\(e\)。因此，非树边的答案就是它两端点之间树上路径上最大边的权值减\(1\)（如果相等则两条边都可以选，不符合“必定成为树边”）。
然后，考虑对于树边\((u,v)\)的情况。把上面的情况反过来考虑，如果有一条非树边\((a,b)\)，树上\(a\)和\(b\)的路径要经过\((u,v)\)，那么只有当任意这样的\((a,b)\)的权值都大于\((u,v)\)时，\((u,v)\)才必定不会被别的边替换下来，也就是必定成为树边。因此，树边的答案就是所有上述\((a,b)\)中权值最小的边的权值减\(1\)。
那么，对于非树边\((u,v,w)\)，我们要查询\((u,v)\)间路径上的最大边权，并且需要用\(w\)来更新这段路径上所有树边的答案（即把这些边的答案与\(w\)取最小值）。注意这两种操作是互不干扰的，不要混淆……
那么这明显就是个树剖+线段树裸题了。区间查最大值和区间修改为最小值都是线段树的基本操作，文末有代码，不再赘述。
好现在开始隆重介绍某位神仙给我讲的倍增做法，比树剖+线段树少一个\(logn\)。以下为了方便叙述，默认\(1\)号点为树根，\(fa[a][i]\)表示\(a\)点往上走\(2^i\)步所到的点。
区间查最大值也是倍增的经典应用，不必多言。区间取最小是这个算法最精妙之处。考虑用\(minn[a][i]\)表示所有一端是\(a\)及其子树，另一端是\(fa[a][i]\)及其祖先的非树边的最小权值。\(minn[a][0]\)就是\(a\)和\(a\)的父亲之间的边的答案。那么，当我们更新\(minn[a][i]\)时，也要尝试更新\(minn[a][i-1]\)和\(minn[fa[a][i-1][i-1]\)（覆盖了大区间的非树边一定会覆盖该区间的子区间），这是一个递归的过程。然而每次修改都递归一次的复杂度是\(O(n)\)的（最坏会被卡到深度为\(logn\)的满二叉树），\(O(nm)\)显然是过不去的。
但是我们要注意两件事。第一，\(minn[a][i]\)只会变小不会变大，且修改之间不会互相影响；第二，全部非树边考虑完后才会查询。基于这两件事，我们可以全部修改尽可能大的区间，最后再一起递归下去。这个操作类似于线段树的pushdown。这一段非常重要和巧妙，单独给出代码。（注意要分层处理，所以\(j\)应当在外层循环）
for (int j = B - 1; j > 0; j--)
for (int i = 1; i <= n; i++)
{
minn[i][j - 1] = min(minn[i][j - 1], minn[i][j]);
minn[fa[i][j - 1]][j - 1] = min(minn[fa[i][j - 1]][j - 1], minn[i][j]);
}
本题其余细节详见下方的代码。
代码：
法1：倍增（\(143\)行，\(561\)ms，\(65200\)KB）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
namespace zyt
{
const int N = 2e5 + 10, M = 2e5 + 10, B = 20, INF = 0x3f3f3f3f;
int n, m;
struct ed
{
int u, v, w, id;
bool in_tree;
bool operator < (const ed &b) const
{
return w < b.w;
}
}e[M];
struct edge
{
int to, w, id;
};
vector<edge> g[N];
int p[N], pre[N], dep[N], maxx[N][B], minn[N][B], fa[N][B], ans[M];
int f(const int x)
{
return x == p[x] ? x : p[x] = f(p[x]);
}
void dfs(const int u, const int f)
{
dep[u] = dep[f] + 1;
fa[u][0] = f;
for (int i = 1; i < B; i++)
{
fa[u][i] = fa[fa[u][i - 1]][i - 1];
maxx[u][i] = max(maxx[u][i - 1], maxx[fa[u][i - 1]][i - 1]);
}
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i].to;
if (v == f)
continue;
pre[v] = g[u][i].id;
maxx[v][0] = g[u][i].w;
dfs(v, u);
}
}
int query_max(int a, int b)
{
int ans = 0;
if (dep[a] < dep[b])
swap(a, b);
for (int i = B - 1; i >= 0; i--)
if (dep[fa[a][i]] >= dep[b])
ans = max(ans, maxx[a][i]), a = fa[a][i];
if (a == b)
return ans;
for (int i = B - 1; i >= 0; i--)
if (fa[a][i] != fa[b][i])
{
ans = max(ans, max(maxx[a][i], maxx[b][i]));
a = fa[a][i], b = fa[b][i];
}
return max(ans, max(maxx[a][0], maxx[b][0]));
}
void change_min(int a, int b, const int w)
{
if (dep[a] < dep[b])
swap(a, b);
for (int i = B - 1; i >= 0; i--)
if (dep[fa[a][i]] >= dep[b])
minn[a][i] = min(minn[a][i], w), a = fa[a][i];
if (a == b)
return;
for (int i = B - 1; i >= 0; i--)
if (fa[a][i] != fa[b][i])
{
minn[a][i] = min(minn[a][i], w);
minn[b][i] = min(minn[b][i], w);
a = fa[a][i];
b = fa[b][i];
}
minn[a][0] = min(minn[a][0], w);
minn[b][0] = min(minn[b][0], w);
}
void Kruskal()
{
for (int i = 1; i <= n; i++)
p[i] = i;
for (int i = 0; i < m; i++)
{
int u = e[i].u, v = e[i].v, x = f(u), y = f(v);
if (x != y)
{
p[x] = y;
g[u].push_back((edge){v, e[i].w, e[i].id});
g[v].push_back((edge){u, e[i].w, e[i].id});
e[i].in_tree = true;
}
}
}
int work()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
memset(minn, INF, sizeof(int[n + 1][B]));
for (int i = 0; i < m; i++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
e[i].id = i;
}
sort(e, e + m);
Kruskal();
dfs(1, 0);
for (int i = 0; i < m; i++)
if (!e[i].in_tree)
{
ans[e[i].id] = query_max(e[i].u, e[i].v) - 1;
change_min(e[i].u, e[i].v, e[i].w);
}
for (int j = B - 1; j > 0; j--)
for (int i = 1; i <= n; i++)
{
minn[i][j - 1] = min(minn[i][j - 1], minn[i][j]);
minn[fa[i][j - 1]][j - 1] = min(minn[fa[i][j - 1]][j - 1], minn[i][j]);
}
for (int i = 2; i <= n; i++)
ans[pre[i]] = minn[i][0] - 1;
for (int i = 0; i < m; i++)
if (ans[i] < INF - 1)
cout << ans[i] << ' ';
else
cout << "-1 ";
return 0;
}
}
int main()
{
return zyt::work();
}
法2：树链剖分+线段树（\(230\)行，\(826\)ms，\(34600\)KB）
（我很傻地第一次漏了size[u]+=size[v]搞成了随机剖分还以为是因为卡常所以T……菜死我了）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
namespace zyt
{
const int N = 2e5 + 10, M = 2e5 + 10, B = 20, INF = 0x3f3f3f3f;
int n, m;
struct ed
{
int u, v, w, id;
bool in_tree;
bool operator < (const ed &b) const
{
return w < b.w;
}
}e[M];
struct edge
{
int to, w, id;
};
vector<edge> g[N];
int p[N], pre[N], pre_w[N], dep[N], w[N], son[N], size[N], dfn[N], top[N], fa[N], ans[N], cnt;
int f(const int x)
{
return x == p[x] ? x : p[x] = f(p[x]);
}
namespace Tree_Chain_Cut
{
void dfs1(const int u, const int f)
{
dep[u] = dep[f] + 1;
fa[u] = f;
size[u] = 1;
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i].to;
if (v == f)
continue;
pre[v] = g[u][i].id;
pre_w[v] = g[u][i].w;
dfs1(v, u);
if (size[v] > size[son[u]])
son[u] = v;
size[u] += size[v];
}
}
void dfs2(const int u, const int t)
{
dfn[u] = ++cnt;
w[dfn[u]] = pre_w[u];
top[u] = t;
if (son[u])
dfs2(son[u], t);
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i].to;
if (dfn[v])
continue;
dfs2(v, v);
}
}
namespace Segment_Tree
{
struct node
{
int minn, maxx, tag;
}tree[N * 4];
inline void update(const int rot)
{
tree[rot].minn = min(tree[rot << 1].minn, tree[rot << 1 | 1].minn);
tree[rot].maxx = max(tree[rot << 1].maxx, tree[rot << 1 | 1].maxx);
}
inline void pushdown(const int rot)
{
int tag = tree[rot].tag;
tree[rot << 1].minn = min(tree[rot << 1].minn, tag);
tree[rot << 1].tag = min(tree[rot << 1].tag, tag);
tree[rot << 1 | 1].minn = min(tree[rot << 1 | 1].minn, tag);
tree[rot << 1 | 1].tag = min(tree[rot << 1 | 1].tag, tag);
tree[rot].tag = INF;
}
void build(const int rot, const int lt, const int rt)
{
tree[rot].minn = tree[rot].tag = INF;
if (lt == rt)
{
tree[rot].maxx = w[lt];
return;
}
int mid = (lt + rt) >> 1;
build(rot << 1, lt, mid);
build(rot << 1 | 1, mid + 1, rt);
update(rot);
}
void change_min(const int rot, const int lt, const int rt, const int ls, const int rs, const int w)
{
if (ls <= lt && rt <= rs)
{
tree[rot].minn = min(tree[rot].minn, w);
tree[rot].tag = min(tree[rot].tag, w);
return;
}
pushdown(rot);
int mid = (lt + rt) >> 1;
if (ls <= mid)
change_min(rot << 1, lt, mid, ls, rs, w);
if (rs > mid)
change_min(rot << 1 | 1, mid + 1, rt, ls, rs, w);
update(rot);
}
int query_max(const int rot, const int lt, const int rt, const int ls, const int rs)
{
if (ls <= lt && rt <= rs)
return tree[rot].maxx;
pushdown(rot);
int mid = (lt + rt) >> 1, ans = 0;
if (ls <= mid)
ans = max(ans, query_max(rot << 1, lt, mid, ls, rs));
if (rs > mid)
ans = max(ans, query_max(rot << 1 | 1, mid + 1, rt, ls, rs));
return ans;
}
int query_min(const int rot, const int lt, const int rt, const int pos)
{
if (lt == rt)
return tree[rot].minn;
pushdown(rot);
int mid = (lt + rt) >> 1, ans = 0;
if (pos <= mid)
return query_min(rot << 1, lt, mid, pos);
else
return query_min(rot << 1 | 1, mid + 1, rt, pos);
return ans;
}
}
int query_max(int a, int b)
{
int ans = 0;
while (top[a] != top[b])
{
if (dep[top[a]] < dep[top[b]])
swap(a, b);
ans = max(ans, Segment_Tree::query_max(1, 1, n, dfn[top[a]], dfn[a]));
a = fa[top[a]];
}
if (a != b)
{
if (dep[a] < dep[b])
swap(a, b);
ans = max(ans, Segment_Tree::query_max(1, 1, n, dfn[b] + 1, dfn[a]));
}
return ans;
}
int query_min(const int a)
{
return Segment_Tree::query_min(1, 1, n, dfn[a]);
}
void change_min(int a, int b, const int w)
{
while (top[a] != top[b])
{
if (dep[top[a]] < dep[top[b]])
swap(a, b);
Segment_Tree::change_min(1, 1, n, dfn[top[a]], dfn[a], w);
a = fa[top[a]];
}
if (a != b)
{
if (dep[a] < dep[b])
swap(a, b);
Segment_Tree::change_min(1, 1, n, dfn[b] + 1, dfn[a], w);
}
}
}
void Kruskal()
{
for (int i = 1; i <= n; i++)
p[i] = i;
for (int i = 0; i < m; i++)
{
int u = e[i].u, v = e[i].v, x = f(u), y = f(v);
if (x != y)
{
p[x] = y;
g[u].push_back((edge){v, e[i].w, e[i].id});
g[v].push_back((edge){u, e[i].w, e[i].id});
e[i].in_tree = true;
}
}
}
int work()
{
using namespace Tree_Chain_Cut;
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
e[i].id = i;
}
sort(e, e + m);
Kruskal();
dfs1(1, 0);
dfs2(1, 1);
Segment_Tree::build(1, 1, n);
for (int i = 0; i < m; i++)
if (!e[i].in_tree)
{
ans[e[i].id] = query_max(e[i].u, e[i].v) - 1;
change_min(e[i].u, e[i].v, e[i].w);
}
for (int i = 2; i <= n; i++)
ans[pre[i]] = query_min(i) - 1;
for (int i = 0; i < m; i++)
if (ans[i] < INF - 1)
cout << ans[i] << ' ';
else
cout << "-1 ";
return 0;
}
}
int main()
{
return zyt::work();
}