正題

luogu 4374

---

題目大意

給你一棵樹，還有若干邊，每條邊有一定代價，問你刪掉樹中的每條邊后，使其成為連通圖的最小代價

---

解題思路

不難發(fā)現(xiàn)，一條邊只對兩個端點在樹中的路徑上的邊有貢獻（即刪去樹中的這些邊，連這條邊才有用）

那么就是對樹中的鏈進行操作

那么用樹鏈剖分，把邊的信息存在深度大的點上即可

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 50100 using namespace std; int n, m, x, y, z, w, tot, v[N], s[N], hs[N], fa[N], xx[N], yy[N], anc[N], dep[N], head[N]; struct rec {int to, next; }a[N<<1]; struct Tree//線段樹 {int a[N<<3]; void build(int x, int l, int r){a[x] = 2147483647;if (l == r) return;int mid = l + r >> 1;build(x * 2, l, mid);build(x * 2 + 1, mid + 1, r);}void down(int x){a[x * 2] = min(a[x * 2], a[x]);a[x * 2 + 1] = min(a[x * 2 + 1], a[x]);return;}void add(int x, int L, int R, int l, int r, int y){if (L == l && R == r){a[x] = min(a[x], y);return;}down(x);int mid = L + R >> 1;if (r <= mid) add(x * 2, L, mid, l, r, y);else if (l > mid) add(x * 2 + 1, mid + 1, R, l, r, y);else add(x * 2, L, mid, l, mid, y), add(x * 2 + 1, mid + 1, R, mid + 1, r, y);return;}int ask(int x, int L, int R, int y){if (L == y && y == R) return a[x];down(x);int mid = L + R >> 1;if (y <= mid) return ask(x * 2, L, mid, y);else return ask(x * 2 + 1, mid + 1, R, y);} }T; void add(int x, int y) {a[++tot].to = y;a[tot].next = head[x];head[x] = tot;return; } void dfs1(int x)//樹鏈剖分 {s[x] = 1;for (int i = head[x]; i; i = a[i].next)if (!s[a[i].to]){dep[a[i].to] = dep[x] + 1;fa[a[i].to] = x;dfs1(a[i].to);s[x] += s[a[i].to];if (s[a[i].to] > s[hs[x]]) hs[x] = a[i].to; }return; } void dfs2(int x) {v[x] = ++w;if (hs[x]){anc[hs[x]] = anc[x]; dfs2(hs[x]);}for (int i = head[x]; i; i = a[i].next)if (a[i].to != fa[x] && a[i].to != hs[x]){anc[a[i].to] = a[i].to;dfs2(a[i].to);}return; } void solve(int x, int y, int z) {int fx = anc[x], fy = anc[y];while(fx != fy){if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);T.add(1, 1, n, v[fx], v[x], z);x = fa[fx];fx = anc[x];}if (x != y){if (dep[x] > dep[y]) swap(x, y);T.add(1, 1, n, v[hs[x]], v[y], z);//把邊存在深度大的點上，所以最上面的一個點不加}return; } int main() {scanf("%d%d", &n, &m);T.build(1, 1, n);for (int i = 1; i < n; ++i){scanf("%d%d", &xx[i], &yy[i]);add(xx[i], yy[i]);add(yy[i], xx[i]);}fa[1] = anc[1] = dep[1] = 1;dfs1(1);dfs2(1);for (int i = 1; i <= m; ++i){scanf("%d%d%d", &x, &y, &z);solve(x, y, z);}for (int i = 1; i < n; ++i){if (dep[xx[i]] < dep[yy[i]]) swap(xx[i], yy[i]);int g = T.ask(1, 1, n, v[xx[i]]);if (g <= 1000000000) printf("%d\n", g);else puts("-1");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【树链剖分】Disruption P（luogu 4374）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。