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/89766333
8、对于将一个图变成一棵树和若干条边我们可以用并查集来操作
#include <bits/stdc++.h> using namespace std; #define ll long long #define lson left,mid,k<<1 #define rson mid+1,right,k<<1|1 #define imid int mid=(left+right)/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 pair<int,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--) { map<Pair, int>mp; vector<ll>ans; 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 */