P3250 [HNOI2016]網絡

給定一棵樹，有三種操作：

• 給定$u,v,w$，表示$u,v$路徑上有一個重要度為$w$的請求，
• 給定$t$，第$t$個發生的請求結束，
• 給定一個$x$，假設$x$發生故障，未被影響的請求的最大重要度為多少，如果沒有請求則輸出$?1$。

可以考慮二分答案，如果大于等于$mid$的請求都經過了這個點，那么答案一定是小于$mid$的，

接下來問題轉換為，如何判斷大于等于$mid$的請求是否都經過了這個點，可以考慮樹上差分，對區間整體修改，

由于有多組詢問，如果每次單獨$judge$復雜度將會是$O(n^2{\log }^{2}n)$，的，所以可以考慮整體二分，做到復雜度是$O(n{\log }^{2}n)$的。

#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10;int head[N], to[N], nex[N], cnt = 1;int son[N], sz[N], dep[N], fa[N], rk[N], id[N], top[N], tot;int sum[N], a[N], ans[N], n, m, num;int A[N], B[N], V[N];struct Res {int x, y, f, ff, v, id, type; }q[N], q1[N], q2[N];inline int lowbit(int x) {return x & (-x); }void update(int x, int v) {while (x <= n) {sum[x] += v;x += lowbit(x);} }int query(int x) {int ans = 0;while (x) {ans += sum[x];x -= lowbit(x);}return ans; }void add(int x, int y) {to[cnt] = y;nex[cnt] = head[x];head[x] = cnt++; }void dfs1(int rt, int f) {fa[rt] = f, dep[rt] = dep[f] + 1, sz[rt] = 1, rk[++tot] = rt, id[rt] = tot;for (int i = head[rt]; i; i = nex[i]) {if (to[i] == f) {continue;}dfs1(to[i], rt);sz[rt] += sz[to[i]];if (!son[rt] || sz[son[rt]] < sz[to[i]]) {son[rt] = to[i];}} }void dfs2(int rt, int tp) {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]);} }int lca(int x, int y) {while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) {swap(x, y);}x = fa[top[x]];}return dep[x] < dep[y] ? x : y; }void solve(int l, int r, int L, int R) {if (L > R || l > r) {return ;}if (l == r) {for (int i = L; i <= R; i++) {if (q[i].type == 2) {ans[q[i].id] = a[l];}}return ;}int mid = l + r >> 1, cnt1 = 0, cnt2 = 0, sum = 0;for (int i = L; i <= R; i++) {if (q[i].type == 1) {if (q[i].v > a[mid]) {sum += q[i].id;update(id[q[i].x], q[i].id), update(id[q[i].y], q[i].id), update(id[q[i].f], -q[i].id);if (q[i].ff) {update(id[q[i].ff], -q[i].id);}q2[++cnt2] = q[i];}else {q1[++cnt1] = q[i];}}else {int cur = query(id[q[i].x] + sz[q[i].x] - 1) - query(id[q[i].x] - 1);if (cur == sum) {q1[++cnt1] = q[i];}else {q2[++cnt2] = q[i];}}}for (int i = 1; i <= cnt2; i++) {if (q2[i].type == 1) {update(id[q2[i].x], -q2[i].id), update(id[q2[i].y], -q2[i].id), update(id[q2[i].f], q2[i].id);if (q2[i].ff) {update(id[q2[i].ff], q2[i].id);}}}for (int i = 1; i <= cnt1; i++) {q[L + i - 1] = q1[i];}for (int i = 1; i <= cnt2; i++) {q[L + cnt1 + i - 1] = q2[i];}solve(l, mid, L, L + cnt1 - 1), solve(mid + 1, r, L + cnt1, R); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d %d", &n, &m);for (int i = 1, x, y; i < n; i++) {scanf("%d %d", &x, &y);add(x, y);add(y, x);}dfs1(1, 0);dfs2(1, 1);for (int i = 1, op, x; i <= m; i++) {scanf("%d", &op);if (op == 0) {scanf("%d %d %d", &A[i], &B[i], &V[i]);a[++num] = V[i];int u = A[i], v = B[i], f = lca(u, v), ff = fa[f];q[i] = {u, v, f, ff, V[i], 1, 1};}else if (op == 1) {scanf("%d", &x);q[i] = q[x];q[i].id = -1;}else {scanf("%d", &x);A[i] = 0x3f3f3f3f;q[i] = {x, 0, 0, 0, 0, i, 2};}}sort(a + 1, a + 1 + num);num = unique(a + 1, a + 1 + num) - (a + 1);a[0] = -1;solve(0, num, 1, m);for (int i = 1; i <= m; i++) {if (A[i] == 0x3f3f3f3f) {printf("%d\n", ans[i]);}}return 0; }

總結

以上是生活随笔為你收集整理的P3250 [HNOI2016]网络（整体二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

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