异或路径对 题解

注意到异或有一个性质，就是异或两次同一个数相当于没有异或，所以对于任意两个点，一个简单路径的异或值和带上很多祖先的异或值其实是相等的。

所以我们可以求出每个点到根节点的异或值，然后枚举计算即可。

边转点。

#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
vector <pair <int, int>> v2[5005];
vector <int> v[5005];
int a[5005];
int n;
void dfs(int cur, int fa){
	for(auto i:v2[cur]){
		if(i.first == fa) continue;
		a[i.first] = i.second;
		a[i.first] ^= a[cur];
		dfs(i.first, cur);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++){
		int x, y, z;
		cin >> x >> y >> z;
		v2[x].push_back({y, z});
		v2[y].push_back({x, z});
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1, 0);
	int ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			ans += (a[i] ^ a[j]) % mod;
		}
	}
	cout << ans % mod << '\n';

	return 0;
}

时间复杂度：$O(n^2)$。

注意到瓶颈在于计算异或和，与树无关。所以我们可以不考虑树的部分，只对计算部分进行优化。

考虑拆位。我们可以记录前面的数第 $j$ 位为 $0$ 的个数与为 $1$ 的个数，按照 $A_i$ 的第 $j$ 位计算即可。

记得开 __int128。

#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
vector <pair <int, int>> v2[200005];
vector <int> v[200005];
int a[200005];
int cnt0[60], cnt1[60];
int n;
void dfs(int cur, int fa){
	for(auto i:v2[cur]){
		if(i.first == fa) continue;
		a[i.first] = i.second;
		a[i.first] ^= a[cur];
		dfs(i.first, cur);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++){
		int x, y, z;
		cin >> x >> y >> z;
		v2[x].push_back({y, z});
		v2[y].push_back({x, z});
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1, 0);
	int ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 60; j++){
			if(a[i] >> j & 1) ans += (__int128(cnt0[j]) << j) % mod, cnt1[j]++;
			else ans += (__int128(cnt1[j]) << j) % mod, cnt0[j]++;
			ans %= mod;
		}
	}
	cout << ans << '\n';

	return 0;
}

时间复杂度：$O(n\log V)$，其中 $V=2^{60}$。