ABC302Ex Ball Collector (可撤销并查集)

作者：XiaoQuQu，发表于 Thu Feb 22 2024。

首先我们分析一下，如果我们已经知道了要走哪些点，我们可以怎么做。

考虑将 $a_i,b_i$ 之间连边，发现题目可以被转化为给定一个图，要求对于每条边将其一个顶点染色，问最多能将多少个点染色。

于是我们对于每个连通块分开来考虑。对于一个连通块，注意到我们不能将每个顶点染色当且仅当这个连通块是树，且此时可以染色的定点数量为连通块大小减一，如下：

如果当前连通块是树，则我们可以固定一个点作为根节点，其余所有非根节点，用它连向父亲的那条边对他进行染色。
如果当前连通块不是树，则我们可以求出他的一个生成树，以一个在环中的节点作为根节点，以 (1) 的方案将这个连通块除了这个根节点以外的点染色，接下来用这个环上的与根节点连接的非树边将这个根节点染色。

所以问题就被我们转换成了，需要维护每个连通块是否为树，并且维护答案。因为要求最短路径，所以我们可以在给定的树上以节点 $1$ 为根进行 DFS，于是从 $1$ 到 $x$ 的最短路径就是链上的点。问题就进一步转换成：每次需要在图中加入一条边 $a_i,b_i$ ，询问有多少个连通块与其中有多少个是树。发现可撤销并查集可以做到：在合并/撤销的时候维护一下每个连通块里的边的数量，最终根据边的数量与点的数量判断是否为树即可。

最终时间复杂度 $O(n \log n)$ ，其中 $\log n$ 是可撤销并查集的复杂度。

const int MAXN = 4e5 + 5;
int n, fa[MAXN], a[MAXN], b[MAXN], sz[MAXN], ecnt[MAXN], now, ans[MAXN];
stack<pair<int, int>> st;
vector<int> T[MAXN];

int find(int x) {
	if (fa[x] == x) return x;
	else return find(fa[x]);
}

void merge(int u, int v) {
	if (sz[v] > sz[u]) swap(u, v);
	st.push(make_pair(u, v));
	fa[v] = u;
	sz[u] += sz[v];
	ecnt[u] += ecnt[v] + 1;
}

void undo() {
	int u = st.top().first, v = st.top().second;
	st.pop();
	fa[v] = v;
	ecnt[u] -= ecnt[v] + 1;
	sz[u] -= sz[v];
}

void dfs(int x, int fat) {
	int f1 = find(a[x]), f2 = find(b[x]);
	bool merged = false;
	int add = 0;
	if (f1 == f2) {
		ecnt[f1]++;
		if (sz[f1] == ecnt[f1]) now++, add = 1;
	}
	else {
		if (!(ecnt[f1] >= sz[f1] && ecnt[f2] >= sz[f2])) {
			now++;
			add = 1;
		}
		merge(f1, f2);
		merged = true;
	}
	if (x != 1) ans[x] = now;
	for (auto u:T[x]) {
		if (u == fat) continue;
		dfs(u, x);
	}
	if (merged) undo();
	else ecnt[f1]--;
	now -= add;
}

void work() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i];
	}
	for (int u, v, i = 1; i < n; ++i) {
		cin >> u >> v;
		T[u].push_back(v);
		T[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
	dfs(1, 0);
	for (int i = 2; i <= n; ++i) cout << ans[i] << ' ';
	cout << endl;
}