hdu 5458 Stability （并查集+线段树+树链剖分（边权））

题意有一个n个点m条边的图有q次操作操作1删掉一条a b之间的边操作2询问a b之间的必要边必要边指的是从a到b必须要经过的边。题目说明了在任何情况下保证整个图的连通思路1、如果要直接计算图中两点联通的必要边的话显然不太可行2、那我们把完成所有操作后的图看成一棵树和几条边那么对应的操作就变成了加边和询问3、树上任意两点保证有且只有一条路径并且如果对于树询问必要边的话就是路径上的边数4、对于操作1我们给树上两点加上一条路径就意味着这两个点和他们路径上的点这些点之间的任意两点可以通过两条路到达即没有必要边所以对于操作1我们只需要将两点之间的路径的权值全部改为 0 就可以。5、对于操作2我们只需要查询一下两点在树上的距离就可以。6、整合一下整个题目就变成了先求出最后的图并且将最后的图变成一棵树加上若干条边对于若干条边用操作1将这些边的两个端点之间的距离设为0反向询问对于操作1将这两个点之间的距离设为0对于操作2查询这两点在树上的距离7、所以大概就是 并查集线段树树链剖分边权 https://blog.csdn.net/qq_41608020/article/details/897663338、对于将一个图变成一棵树和若干条边我们可以用并查集来操作#include bits/stdc.h using namespace std; #define ll long long #define lson left,mid,k1 #define rson mid1,right,k1|1 #define imid int mid(leftright)/2; const ll MAXN 100005; struct edge { int to; int nex; }e[MAXN * 2]; int head[MAXN], tot; int n, m, q; int fa[MAXN], son[MAXN], deep[MAXN], num[MAXN]; int top[MAXN], p[MAXN], fp[MAXN]; int pos; int ql, qr; ll val; void init() { tot 0; memset(head, -1, sizeof(head)); pos 1; memset(son, -1, sizeof(son)); } void add(int a, int b) { e[tot] edge{ b,head[a] }; head[a] tot; } void dfs1(int u, int pre, int dep) { deep[u] dep; fa[u] pre; num[u] 1; for (int i head[u]; i 1; i e[i].nex) { int v e[i].to; if (v ! pre) { dfs1(v, u, dep 1); num[u] num[v]; if (son[u] -1 || num[son[u]] num[v]) son[u] v; } } } void dfs2(int u, int sp) { top[u] sp; p[u] pos; fp[p[u]] u; if (son[u] -1) return; dfs2(son[u], sp); for (int i head[u]; i 1; i e[i].nex) { int v e[i].to; if (v ! son[u] v ! fa[u]) dfs2(v, v); } } struct node { int l; int r; ll sum; int mark; }que[MAXN * 4]; void up(int k) { que[k].sum que[k 1].sum que[k 1 | 1].sum; } void down(int k) { if (que[k].mark) { que[k 1].mark que[k].mark; que[k 1 | 1].mark que[k].mark; que[k 1].sum 0; que[k 1 | 1].sum 0; que[k].mark 0; } } void build(int left 1, int right pos, int k 1) { que[k].l left; que[k].r right; que[k].mark 0; if (left right) return; imid; build(lson); build(rson); } void update(int left 1, int right pos, int k 1) { if (qr left || right ql) return; if (ql left right qr) { if (val 0) { que[k].mark 1; que[k].sum 0; } else { que[k].sum 1; } return; } down(k); imid; update(lson); update(rson); up(k); } ll query(int left 1, int right pos, int k 1) { if (qr left || right ql) return 0; if (ql left right qr) return que[k].sum; down(k); imid; return query(lson) query(rson); } void change(int u, int v) { int f1 top[u], f2 top[v]; while (f1 ! f2) { if (deep[f1] deep[f2]) { swap(f1, f2); swap(u, v); } ql p[f1]; qr p[u]; val 0; update(); u fa[f1]; f1 top[u]; } if (u v) return; if (deep[u] deep[v]) swap(u, v); ql p[son[u]]; qr p[v]; val 0; update(); } ll changes(int u, int v) { ll res 0; int f1 top[u], f2 top[v]; while (f1 ! f2) { if (deep[f1] deep[f2]) { swap(f1, f2); swap(u, v); } ql p[f1]; qr p[u]; res query(); u fa[f1]; f1 top[u]; } if (u v) return res; if (deep[u] deep[v]) swap(u, v); ql p[son[u]]; qr p[v]; res query(); return res; } #define Pair pairint,int int in[MAXN][3]; int op[MAXN][3]; int ques[MAXN]; int preop[MAXN][2]; int qq; void initbcj() { qq 0; for (int i 1; i n; i) ques[i] i; } int getf(int k) { return ques[k] k ? k : ques[k] getf(ques[k]); } void merge(int a, int b) { ques[getf(a)] getf(b); } int main() { int T, cas 1; scanf(%d, T); while (T--) { mapPair, intmp; vectorllans; scanf(%d%d%d, n, m, q); init(); initbcj(); for (int i 0; i m; i) { scanf(%d%d, in[i][0], in[i][1]); if (in[i][0] in[i][1]) swap(in[i][0], in[i][1]); mp[Pair{ in[i][0],in[i][1] }]; //add(in[i][0], in[i][1]); //add(in[i][1], in[i][0]); } for (int i 0; i q; i) { scanf(%d%d%d, op[i][0], op[i][1], op[i][2]); if (op[i][1] op[i][2]) swap(op[i][1], op[i][2]); if (op[i][0] 1) mp[Pair{ op[i][1],op[i][2] }]--; } //重新做边 m 0; for (auto it mp.begin(); it ! mp.end(); it) { if (it-second ! 0) { int q getf(it-first.first), w getf(it-first.second); if (q ! w)//树 { add(it-first.first, it-first.second); add(it-first.second, it-first.first); in[m][0] it-first.first; in[m][1] it-first.second; in[m][2] it-second; m; merge(it-first.first, it-first.second); } else//若干条边 { preop[qq][0] it-first.first; preop[qq][1] it-first.second; qq; } } } dfs1(1, 0, 0); dfs2(1, 1); build(); for (int i 0; i m; i) { if (deep[in[i][0]] deep[in[i][1]]) swap(in[i][0], in[i][1]); ql p[in[i][1]]; qr ql; val in[i][2]; //如果是重边和自环就没有必要边 if (val 1 || in[i][0] in[i][1]) val 0; update(); } //preop set 0 若干条边 for (int i 0; i qq; i) change(preop[i][0], preop[i][1]); for (int i q - 1; i 0; i--) { if (op[i][0] 1) { ql op[i][1]; qr op[i][2]; change(ql, qr); } else { ql op[i][1]; qr op[i][2]; ll res changes(ql, qr); ans.push_back(res); } } printf(Case #%d:\n, cas); int len ans.size(); for (int i len - 1; i 0; i--) { printf(%lld\n, ans[i]); } } } /* 1 5 6 5 1 2 1 4 2 4 2 3 4 5 2 4 2 2 4 2 1 4 1 1 2 2 2 4 2 1 2 */