CF1709E XOR Tree

link

Solution:

PART 1: 转化

首先套路地预处理出每个节点到根节点（\(1\) 号节点）路径上的点权异或和 \(w[u]\) 。

可以发现题意容易转化为：给定一棵 \(n\) 个节点的树，问你最少可以把它分成多少个联通块，使得每个连通块中的节点两两路径上的异或和不为 0。

易知对于一个节点，若它要被割分出原来的树，那么一定是在它的子树中有两个点对 \((x,y)\) 没有割分出原树且 \(w[x]\) \(\rm xor\) \(w[y]\) \(\rm xor\) \(a[\rm LCA(x,y)] = 0\)。

PRAT 2：暴力

考虑朴素做法：对每个节点开一个 \(\rm set\) 记录每个节点子树中没有被割分出去的所有节点的 \(w\) 值。枚举 \(\rm LCA(x,y)\)（令它为 \(u\)），如果对于节点 \(u\) 的儿子节点 \(v\)，可以在 \(u\) 的 \(\rm set\) 中找到一个节点 \(t\)，使得 \(w[t]\) \(\rm xor\) \(w[v]\) \(\rm xor\) \(a[u] = 0\) 。那么就一定要将点 \(u\) 割分出去。

具体来讲，我们暴力的合并节点 \(u\) 的所有儿子的 \(\rm set\)，并且枚举其中的点 \(t\) ，若可以在 \(v\) 的 \(\rm set\) 中找到一个节点 \(t\) ，使得 \(w[t]\) \(\rm xor\) \(w[v]\) \(\rm xor\) \(a[u] = 0\)，那么清空 \(u\) 的 \(\rm set\)，并使答案加一。

此时的最坏时间复杂度会在树是一个链的情况下退化成 \(O(n^2 \log n)\)。

PART 3：优化

钦定 \(son[u]\) 为 \(u\) 的所有子节点中子树大小最大的一个，称为重儿子，其他称为轻儿子。可以发现若朴素的合并所有轻儿子，并以 \(O(1)\) 的时间复杂度合并重儿子，那么每个节点至多被朴素合并 \(O(\log n)\) 次。

因此我们对于重儿子直接使用 \(O(1)\) 的 \(\rm swap\) 交换 \(u\) 与 \(son[u]\) 的 \(\rm set\) ，并只查询 \(w[u]\) \(xor\) \(a[u]\) 是否在 \(\rm set\) 中出现，此时相当于合并了。对于轻儿子，直接进行暴力的合并。

这种技巧被我们称作 \(\rm dsu\) \(\rm on\) \(\rm tree\) （树上启发式合并）

时间复杂度降为 \(O(n \log ^2 n)\)

code:

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

const int N = 2e5 + 10;
vector<int>G[N];
set<int>S[N];
int n, a[N], s[N], siz[N], son[N], ans;

void dfs(int u, int fa){
	siz[u] = 1;
	s[u] = a[u] ^ s[fa];
	for(auto v:G[u]){
		if(v == fa)continue;
		dfs(v, u);
		if(siz[v] > siz[son[u]]) son[u] = v;
		siz[u] += siz[v];
	}
	return;
}

void dsu(int u, int fa){
	bool res = 0;
	if(son[u]){
		dsu(son[u], u);
		if(S[son[u]].find(s[u] ^ a[u]) != S[son[u]].end()) res = 1;
		swap(S[u], S[son[u]]);
	}
	S[u].insert(s[u]);
	for(auto v:G[u]){
		if(v != fa && v != son[u]){
			dsu(v, u);
			for(auto t:S[v]) if(S[u].find(t ^ a[u]) != S[u].end()) res = 1;
			for(auto t:S[v]) S[u].insert(t);
		}
	}
	if(res){
		//cout << u << " " << res << "\n";	
		ans++;
		S[u].clear();
	}
	return;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++)cin >> a[i];
	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1, 0);
	dsu(1, 0);
	cout << ans;
	
	return 0;
}