E - Xor Distances

本文主要是介绍E - Xor Distances，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

树和 xor 有些地方 很契合🔥。。
比如树上距离。。很容易想到减去lca公共的那段。
而xor 他异或 刚好也是会抵消公共部分的。。。
题目链接

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128_t
#define ar array<int, 2>
#define arr array<int, 3>7
int  n, m, k, inf = 1LL << 61, mod = 1e9 + 7;
const int N = 5e5 + 50;
vector<ar>mp[N];
int a[N];
void dfs(int u, int p, int cur) {a[u] = cur;for (auto[v, z] : mp[u]) {if (v == p)continue;dfs(v, u, cur ^ z);}
};
void solve() {cin >> n;for (int i = 1; i < n; ++i) {int x, y, z;cin >> x >> y >> z;mp[x].push_back({y, z});mp[y].push_back({x, z});}dfs(1, 0, 0);int ans = 0;for (int i = 0; i <= 60; ++i) {int cnt = 0;for (int j = 1; j <= n; ++j)cnt += a[j] >> i & 1;// 这个大数取模会溢出的 要先%mod。。。尼玛。。ans += (1LL << i) % mod * cnt % mod * (n - cnt) % mod ;ans %= mod;// ans+=cnt*(n-cnt);// 1多少个。。0有多少个。。两两组合多少个。。}cout << ans;
};//这题。。。挺牛逼的。。
// 1  树上路径亦或。有一个技巧就是 [a,b]=[root,a]^[root,b];. 问题就换成了数组内任意两个数的亦或的和
// 2 数组任意两个数的亦或和。。也有一个技巧。。就是按位计算贡献。2^i 。。 i位=1的*i位=0的🔥。。就是2^i的贡献。。signed main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);
#ifdef DEBUGfreopen("../1.in", "r", stdin);
#endif//init_f();//init();//expr();// int T; cin >> T; while(T--)solve();return 0;
}

这篇关于E - Xor Distances的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---