本文共 5382 字，大约阅读时间需要 17 分钟。
题目链接：
给你n个点，m条边，q个操作，操作1是删边，操作2是问u到v之间的割边有多少条。
这题要倒着做才容易，倒着加边。
因为这题最后保证所有的点一定连通，所以可以构建一棵树，树链剖分一下。要是u到v之间只有一条边，那便是一条割边。而加边的话，就是将u到v之间的边权都+1，边权等于1的话是桥，大于1的话就不是了。所以我们初始化树的时候，可以将边权初始化为1，加边操作将边权赋值为0。求u到v的割边个数的话，就是求u到v的和。
中间存边我用multiset( map 超时)，然后用并查集判断是不是一棵完整的树从而看情况加边。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std; 14 typedef long long LL; 15 typedef pair P; 16 const int N = 1e5 + 5; 17 struct Edge { 18 int next, to; 19 }edge[N << 1]; 20 multiset myset; //存 构建的树的边 21 int head[N], tot; 22 int pre[N], son[N], dep[N], size[N], cnt; //son:重儿子 23 int top[N], id[N]; 24 int uu[N], vv[N], c[N]; //q个操作c uu vv 25 int x[N], y[N]; //开始输入的m条边x y 26 int ans[N]; //答案 27 int par[N]; //并查集 28 29 void init(int n) { 30 for(int i = 1; i <= n; ++i) { 31 par[i] = i; 32 head[i] = -1; 33 } 34 tot = cnt = 0; 35 myset.clear(); 36 } 37 38 inline void add(int u, int v) { 39 edge[tot].next = head[u]; 40 edge[tot].to = v; 41 head[u] = tot++; 42 } 43 44 inline int search(int n) { 45 if(n == par[n]) 46 return n; 47 return par[n] = search(par[n]); 48 } 49 50 void dfs1(int u, int p, int d) { 51 dep[u] = d, size[u] = 1, son[u] = u, pre[u] = p; 52 for(int i = head[u]; ~i; i = edge[i].next) { 53 int v = edge[i].to; 54 if(v == p) 55 continue; 56 dfs1(v, u, d + 1); 57 if(size[v] >= size[son[u]]) 58 son[u] = v; 59 size[u] += size[v]; 60 } 61 } 62 63 void dfs2(int u, int p, int t) { 64 top[u] = t, id[u] = ++cnt; 65 if(son[u] != u) 66 dfs2(son[u], u, t); 67 for(int i = head[u]; ~i; i = edge[i].next) { 68 int v = edge[i].to; 69 if(v == p || v == son[u]) 70 continue; 71 dfs2(v, u, v); 72 } 73 } 74 75 struct SegTree { 76 int l, r, val, lazy, mid; 77 }T[N << 2]; 78 79 void build(int p, int l, int r) { 80 T[p].mid = (l + r) >> 1; 81 T[p].l = l, T[p].r = r, T[p].lazy = 1; 82 if(l == r) { 83 T[p].val = 1; 84 return ; 85 } 86 build(p << 1, l, T[p].mid); 87 build((p << 1)|1, T[p].mid + 1, r); 88 T[p].val = T[p << 1].val + T[(p << 1)|1].val; 89 } 90 91 inline void pushdown(int p) { 92 int ls = p << 1, rs = (p << 1)|1; 93 T[ls].lazy = T[rs].lazy = T[ls].val = T[rs].val = 0; 94 T[p].lazy = 1; 95 } 96 97 void update(int p, int l, int r) { 98 if(T[p].val == 0) 99 return ;100 if(T[p].l == l && T[p].r == r) {101 T[p].lazy = T[p].val = 0;102 return ;103 }104 if(!T[p].lazy) {105 pushdown(p);106 }107 if(r <= T[p].mid) {108 update(p << 1, l, r);109 }110 else if(l > T[p].mid) {111 update((p << 1)|1, l, r);112 }113 else {114 update(p << 1, l, T[p].mid);115 update((p << 1)|1, T[p].mid + 1, r);116 }117 T[p].val = T[p << 1].val + T[(p << 1)|1].val;118 }119 120 int query(int p, int l, int r) {121 if(T[p].val == 0)122 return 0;123 if(T[p].l == l && T[p].r == r) {124 return T[p].val;125 }126 if(!T[p].lazy) {127 pushdown(p);128 }129 if(r <= T[p].mid) {130 return query(p << 1 , l , r);131 }132 else if(l > T[p].mid) {133 return query((p << 1)|1 , l , r);134 }135 else {136 return query(p << 1 , l , T[p].mid) + query((p << 1)|1 , T[p].mid + 1 , r);137 }138 }139 140 void change(int u, int v) {141 int fu = top[u], fv = top[v];142 while(fu != fv) {143 if(dep[fu] >= dep[fv]) {144 update(1, id[fu], id[u]);145 u = pre[fu];146 fu = top[u];147 }148 else {149 update(1, id[fv], id[v]);150 v = pre[fv];151 fv = top[v];152 }153 }154 if(u == v)155 return ;156 else if(dep[u] >= dep[v])157 update(1, id[son[v]], id[u]);158 else159 update(1, id[son[u]], id[v]);160 }161 162 int find(int u, int v) {163 int fu = top[u], fv = top[v], res = 0;164 while(fu != fv) {165 if(dep[fu] >= dep[fv]) {166 res += query(1, id[fu], id[u]);167 u = pre[fu];168 fu = top[u];169 }170 else {171 res += query(1, id[fv], id[v]);172 v = pre[fv];173 fv = top[v];174 }175 }176 if(u == v)177 return res;178 else if(dep[u] >= dep[v])179 return res + query(1, id[son[v]], id[u]);180 else181 return res + query(1, id[son[u]], id[v]);182 }183 184 int main()185 {186 int t, n, m, q, u, v;187 scanf("%d", &t);188 for(int ca = 1; ca <= t; ++ca) {189 scanf("%d %d %d", &n, &m, &q);190 init(n);191 for(int i = 1; i <= m; ++i) {192 scanf("%d %d", x + i, y + i);193 if(x[i] > y[i])194 swap(x[i], y[i]);195 myset.insert(make_pair(x[i], y[i])); //先存边196 }197 for(int i = 1; i <= q; ++i) {198 scanf("%d %d %d", c + i, uu + i, vv + i);199 if(uu[i] > vv[i])200 swap(uu[i], vv[i]);201 if(c[i] == 1) {202 auto pos = myset.find(make_pair(uu[i], vv[i])); //去除要删的边203 myset.erase(pos);204 }205 }206 int f = 0;207 for(auto i = myset.begin(); i != myset.end(); ++i) {208 u = search(i->first), v = search(i->second);209 if(u == v) { //不成环210 ++f;211 x[f] = i->first, y[f] = i->second; //此时的x y存的是非树也非删的边212 continue;213 }214 par[u] = v;215 add(i->first, i->second);216 add(i->second, i->first);217 }218 dfs1(1, -1, 0);219 dfs2(1, -1, 1);220 printf("Case #%d:\n", ca);221 build(1, 2, n);222 for(int i = 1; i <= f; ++i) {223 change(x[i], y[i]);224 }225 f = 0;226 for(int i = q; i >= 1; --i) {227 if(c[i] == 1) {228 change(uu[i], vv[i]);229 }230 else {231 ans[++f] = find(uu[i], vv[i]);232 }233 }234 for(int i = f; i >= 1; --i) {235 printf("%d\n", ans[i]);236 }237 }238 return 0;239 }
myset; //存 构建的树的边 21 int head[N], tot; 22 int pre[N], son[N], dep[N], size[N], cnt; //son:重儿子 23 int top[N], id[N]; 24 int uu[N], vv[N], c[N]; //q个操作c uu vv 25 int x[N], y[N]; //开始输入的m条边x y 26 int ans[N]; //答案 27 int par[N]; //并查集 28 29 void init(int n) { 30 for(int i = 1; i <= n; ++i) { 31 par[i] = i; 32 head[i] = -1; 33 } 34 tot = cnt = 0; 35 myset.clear(); 36 } 37 38 inline void add(int u, int v) { 39 edge[tot].next = head[u]; 40 edge[tot].to = v; 41 head[u] = tot++; 42 } 43 44 inline int search(int n) { 45 if(n == par[n]) 46 return n; 47 return par[n] = search(par[n]); 48 } 49 50 void dfs1(int u, int p, int d) { 51 dep[u] = d, size[u] = 1, son[u] = u, pre[u] = p; 52 for(int i = head[u]; ~i; i = edge[i].next) { 53 int v = edge[i].to; 54 if(v == p) 55 continue; 56 dfs1(v, u, d + 1); 57 if(size[v] >= size[son[u]]) 58 son[u] = v; 59 size[u] += size[v]; 60 } 61 } 62 63 void dfs2(int u, int p, int t) { 64 top[u] = t, id[u] = ++cnt; 65 if(son[u] != u) 66 dfs2(son[u], u, t); 67 for(int i = head[u]; ~i; i = edge[i].next) { 68 int v = edge[i].to; 69 if(v == p || v == son[u]) 70 continue; 71 dfs2(v, u, v); 72 } 73 } 74 75 struct SegTree { 76 int l, r, val, lazy, mid; 77 }T[N << 2]; 78 79 void build(int p, int l, int r) { 80 T[p].mid = (l + r) >> 1; 81 T[p].l = l, T[p].r = r, T[p].lazy = 1; 82 if(l == r) { 83 T[p].val = 1; 84 return ; 85 } 86 build(p << 1, l, T[p].mid); 87 build((p << 1)|1, T[p].mid + 1, r); 88 T[p].val = T[p << 1].val + T[(p << 1)|1].val; 89 } 90 91 inline void pushdown(int p) { 92 int ls = p << 1, rs = (p << 1)|1; 93 T[ls].lazy = T[rs].lazy = T[ls].val = T[rs].val = 0; 94 T[p].lazy = 1; 95 } 96 97 void update(int p, int l, int r) { 98 if(T[p].val == 0) 99 return ;100 if(T[p].l == l && T[p].r == r) {101 T[p].lazy = T[p].val = 0;102 return ;103 }104 if(!T[p].lazy) {105 pushdown(p);106 }107 if(r <= T[p].mid) {108 update(p << 1, l, r);109 }110 else if(l > T[p].mid) {111 update((p << 1)|1, l, r);112 }113 else {114 update(p << 1, l, T[p].mid);115 update((p << 1)|1, T[p].mid + 1, r);116 }117 T[p].val = T[p << 1].val + T[(p << 1)|1].val;118 }119 120 int query(int p, int l, int r) {121 if(T[p].val == 0)122 return 0;123 if(T[p].l == l && T[p].r == r) {124 return T[p].val;125 }126 if(!T[p].lazy) {127 pushdown(p);128 }129 if(r <= T[p].mid) {130 return query(p << 1 , l , r);131 }132 else if(l > T[p].mid) {133 return query((p << 1)|1 , l , r);134 }135 else {136 return query(p << 1 , l , T[p].mid) + query((p << 1)|1 , T[p].mid + 1 , r);137 }138 }139 140 void change(int u, int v) {141 int fu = top[u], fv = top[v];142 while(fu != fv) {143 if(dep[fu] >= dep[fv]) {144 update(1, id[fu], id[u]);145 u = pre[fu];146 fu = top[u];147 }148 else {149 update(1, id[fv], id[v]);150 v = pre[fv];151 fv = top[v];152 }153 }154 if(u == v)155 return ;156 else if(dep[u] >= dep[v])157 update(1, id[son[v]], id[u]);158 else159 update(1, id[son[u]], id[v]);160 }161 162 int find(int u, int v) {163 int fu = top[u], fv = top[v], res = 0;164 while(fu != fv) {165 if(dep[fu] >= dep[fv]) {166 res += query(1, id[fu], id[u]);167 u = pre[fu];168 fu = top[u];169 }170 else {171 res += query(1, id[fv], id[v]);172 v = pre[fv];173 fv = top[v];174 }175 }176 if(u == v)177 return res;178 else if(dep[u] >= dep[v])179 return res + query(1, id[son[v]], id[u]);180 else181 return res + query(1, id[son[u]], id[v]);182 }183 184 int main()185 {186 int t, n, m, q, u, v;187 scanf("%d", &t);188 for(int ca = 1; ca <= t; ++ca) {189 scanf("%d %d %d", &n, &m, &q);190 init(n);191 for(int i = 1; i <= m; ++i) {192 scanf("%d %d", x + i, y + i);193 if(x[i] > y[i])194 swap(x[i], y[i]);195 myset.insert(make_pair(x[i], y[i])); //先存边196 }197 for(int i = 1; i <= q; ++i) {198 scanf("%d %d %d", c + i, uu + i, vv + i);199 if(uu[i] > vv[i])200 swap(uu[i], vv[i]);201 if(c[i] == 1) {202 auto pos = myset.find(make_pair(uu[i], vv[i])); //去除要删的边203 myset.erase(pos);204 }205 }206 int f = 0;207 for(auto i = myset.begin(); i != myset.end(); ++i) {208 u = search(i->first), v = search(i->second);209 if(u == v) { //不成环210 ++f;211 x[f] = i->first, y[f] = i->second; //此时的x y存的是非树也非删的边212 continue;213 }214 par[u] = v;215 add(i->first, i->second);216 add(i->second, i->first);217 }218 dfs1(1, -1, 0);219 dfs2(1, -1, 1);220 printf("Case #%d:\n", ca);221 build(1, 2, n);222 for(int i = 1; i <= f; ++i) {223 change(x[i], y[i]);224 }225 f = 0;226 for(int i = q; i >= 1; --i) {227 if(c[i] == 1) {228 change(uu[i], vv[i]);229 }230 else {231 ans[++f] = find(uu[i], vv[i]);232 }233 }234 for(int i = f; i >= 1; --i) {235 printf("%d\n", ans[i]);236 }237 }238 return 0;239 }
写的我比较头痛，调试了比较久...
转载于:https://www.cnblogs.com/Recoder/p/5774848.html
