P11674 [USACO25JAN] Reachable Pairs G - 洛谷 (luogu.com.cn)

赛时很确定自己想到了正解，但死活没优化过去。

现在冷静了想想还是很可惜。

---

发现是一道有关连通性的题，题目求按顺序去掉点前的连通点对，实际就是求连通块。

（答案是各个连通块里选两个点的组合数之和）

很明显我们可以 vector 存边，倒序加点构建并查集 siz 求连通块。

题目中的两个操作，0 是真正的删除，1 可以发现删掉点后连通性不变。

那我们可以把 1 的点看作 “空壳点”，这些点只是作为一个 “联通站”。

只负责将它所在连通块的点连起来，自己本身不计入答案。

那么 siz 一开始等于 0，直到这个点被加进去才为 1。

加 i 的边的时候不仅要加 j > i 的边，s[j] = 1 的也要加。

即使 j 点被删了，但它作为 “联通站” 还是要把周围的点连起来。

最后一开始读入边的时候，如果边的两端都为 1，应该并起来。

因为这两个点的连通性是无论怎么删点都存在的，而 1 和 0 的再 0 点被删之后就不存在了。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 2e5 + 10;
char s[N];
vector<int> G[N];
LL sum; 

int fa[N], siz[N];
int findfa(int x) {
	if (fa[x] == x) {
		return fa[x];
	}
	return fa[x] = findfa(fa[x]);
}

void merge(int x, int y) {
	int tx = findfa(x), ty = findfa(y);
	if (tx != ty) {
		fa[tx] = ty;
		sum += 1ll * siz[tx] * siz[ty];
		siz[ty] += siz[tx];
	}
} 

LL ans[N];

int main () {
	ios::sync_with_stdio(false);
	cin.tie();
	
	int n, m;
	cin >> n >> m;
	cin >> (s + 1);
	
	for (int i = 1; i <= n; i ++) {
		fa[i] = i;
		siz[i] = 0;    //
	}
	sum = 0;
	
	for (int i = 1; i <= m; i ++) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
		if (s[x] == '1' && s[y] == '1') {
			merge(x, y);
		}
	}
	
	for (int i = n; i >= 1; i--) {
		for (int j : G[i]) if (j > i || s[j] == '1'){
			merge(i, j);
		}
		
		int ifa = findfa(i);
		sum += siz[ifa];    // 可达点是 i 到全连通块的点 
		siz[ifa] ++;   // 加点 
		
		ans[i] = sum;
	}
	
	for (int i = 1; i <= n; i ++) {
		cout << ans[i] << "\n";
	}
	return 0;
}