D. Best Edge Weight

給定一個有$n$個點$m$條邊的無向連通圖，有$m$次詢問，每次詢問第$i$條邊的權值最大為多少，這張圖的所有最小生成樹的方案中，一定包含第$i$條邊。

先跑一邊最小生成樹，得到最小生成樹，然后依次統計答案，分兩種情況：

1、這條邊在最小生成樹上

假設這條邊的邊權為$value$，把這條邊斷開，則分成了兩個集合$A,B$，那么有一個性質，從集合$A$連向集合$B$的邊，邊權一定大于等于$value$，

如果從集合$A$連向集合$B$的邊只有一條，則這條邊必定存在，答案為$?1$。

如果從集合$A$連向集合$B$的邊，邊權為$value$的只有一條，則答案為除這條邊以外的最小邊權 - 1。

否則的話，答案就是$value?1$了 。

2、這條邊不在最小生成樹上

考慮找到$u?>v$路徑上權值最大的邊$value$，把這條邊斷開，分成了兩個集合$A,B$，同樣的有一個性質，從集合$A$連向集合$B$的邊，邊權一定大于等于$value$，

所以要使$A,B$集合聯通，且這條邊一定出現，則邊權為$value?1$即可。

對第 2 種情況，可以考慮樹鏈剖分，然后線段樹維護區間最大值即可，單次詢問復雜度$\log n\log n$，考慮如何解決第一種情況。

對第 1 種情況，用線段樹維護一個區間最小值跟區間最小值個數，然后單點查詢最小值個數即可，邊權下放成點權，樹鏈剖分。

#include <bits/stdc++.h> #define mid (l + r >> 1) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define ls rt << 1 #define rs rt << 1 | 1using namespace std;const int N = 2e5 + 10;int head[N], to[N << 1], nex[N << 1], value[N << 1], cnt = 1;int son[N], sz[N], dep[N], fa[N], rk[N], id[N], top[N], tot;int ff[N], vis[N], w[N], ans[N], n, m;struct Res {int u, v, w, id;bool operator < (const Res &t) const {return w < t.w;} }edge[N];void add(int x, int y, int w) {to[cnt] = y;nex[cnt] = head[x];value[cnt] = w;head[x] = cnt++; }int find(int rt) {return ff[rt] == rt ? rt : ff[rt] = find(ff[rt]); }void dfs1(int rt, int f) {fa[rt] = f, dep[rt] = dep[f] + 1, sz[rt] = 1;for (int i = head[rt]; i; i = nex[i]) {if (to[i] == f) {continue;}w[to[i]] = value[i];dfs1(to[i], rt);sz[rt] += sz[to[i]];if (!son[rt] || sz[to[i]] > sz[son[rt]]) {son[rt] = to[i];}} }void dfs2(int rt, int tp) {rk[++tot] = rt, id[rt] = tot, top[rt] = tp;if (!son[rt]) {return ;}dfs2(son[rt], tp);for (int i = head[rt]; i; i = nex[i]) {if (to[i] == fa[rt] || to[i] == son[rt]) {continue;}dfs2(to[i], to[i]);} }void Kruskal() {sort(edge + 1, edge + m + 1);for (int i = 1; i <= n; i++) {ff[i] = i;}for (int i = 1, sum = 0; i <= m && sum < n; i++) {int u = find(edge[i].u), v = find(edge[i].v);if (u == v) {continue;}ff[u] = v, vis[i] = 1, sum++;add(edge[i].u, edge[i].v, edge[i].w);add(edge[i].v, edge[i].u, edge[i].w);}dfs1(1, 0);dfs2(1, 1); }int maxn[N << 2], minn[N << 2], lazy[N << 2];void push_up(int rt) {maxn[rt] = max(maxn[ls], maxn[rs]); }void push_down(int rt) {if (lazy[rt] != 0x3f3f3f3f) {minn[ls] = min(minn[ls], lazy[rt]), minn[rs] = min(minn[rs], lazy[rt]);lazy[ls] = min(lazy[ls], lazy[rt]), lazy[rs] = min(lazy[rs], lazy[rt]);lazy[rt] = 0x3f3f3f3f;} }void build(int rt, int l, int r) {minn[rt] = lazy[rt] = 0x3f3f3f3f;if (l == r) {maxn[rt] = w[rk[l]];return ;}build(lson);build(rson);push_up(rt); }void update(int rt, int l, int r, int L, int R, int v) {if (l >= L && r <= R) {lazy[rt] = min(lazy[rt], v);minn[rt] = min(minn[rt], v);return ;}push_down(rt);if (L <= mid) {update(lson, L, R, v);}if (R > mid) {update(rson, L, R, v);} }int query_max(int rt, int l, int r, int L, int R) {if (l >= L && r <= R) {return maxn[rt];}push_down(rt);int maxn = 0;if (L <= mid) {maxn = max(maxn, query_max(lson, L, R));}if (R > mid) {maxn = max(maxn, query_max(rson, L, R));}return maxn; }int query_min(int rt, int l, int r, int x) {if (l == r) {return minn[rt];}push_down(rt);if (x <= mid) {return query_min(lson, x);}else {return query_min(rson, x);} }void update(int u, int v, int w) {while (top[u] != top[v]) {if (dep[top[u]] < dep[top[v]]) {swap(u, v);}update(1, 1, n, id[top[u]], id[u], w);u = fa[top[u]];}if (u != v) {if (dep[u] > dep[v]) {swap(u, v);}update(1, 1, n, id[u] + 1, id[v], w);} }int query(int u, int v) {int maxn = 0;while (top[u] != top[v]) {if (dep[top[u]] < dep[top[v]]) {swap(u, v);}maxn = max(maxn, query_max(1, 1, n, id[top[u]], id[u]));u = fa[top[u]];}if (u != v) {if (dep[u] > dep[v]) {swap(u, v);}maxn = max(maxn, query_max(1, 1, n, id[u] + 1, id[v]));}return maxn; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d %d", &n, &m);for (int i = 1, u, v, w; i <= m; i++) {scanf("%d %d %d", &u, &v, &w);edge[i] = {u, v, w, i};}Kruskal();build(1, 1, n);for (int i = 1; i <= m; i++) {if (!vis[i]) {update(edge[i].u, edge[i].v, edge[i].w);}}for (int i = 1; i <= m; i++) {if (vis[i]) {int u = edge[i].u, v = edge[i].v;if (dep[u] < dep[v]) {swap(u, v);}int cur = query_min(1, 1, n, id[u]);if (cur == edge[i].w) {ans[edge[i].id] = edge[i].w - 1;}else if (cur == 0x3f3f3f3f) {ans[edge[i].id] = -1;}else {ans[edge[i].id] = cur - 1;}}else {ans[edge[i].id] = query(edge[i].u, edge[i].v) - 1;}}for (int i = 1; i <= m; i++) {printf("%d%c", ans[i], i == m ? '\n' : ' ');}return 0; }

總結

以上是生活随笔為你收集整理的D. Best Edge Weight（最小生成树 + 树链剖分）（Codeforces Round #423 (Div. 1, rated, based on VK Cup Finals)）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。