题目

Codeforces827D

分析

倍增神题……（感谢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(); }