算法
(位运算)
有个结论是路径上的 xor
等于 xor
的深度的 xor
所以我们可以按位考虑,求出路径 xor
为 $1$ 的方案数即可。
双倍经验: Tree paths and their xor values
C++ 代码
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
using namespace atcoder;
using mint = modint1000000007;
int n;
struct Edge {
int to;
ll w;
Edge(int to = 0, ll w = 0): to(to), w(w) {}
};
vector<vector<Edge>> g;
int dfs(int v, int x = 0, int p = -1) {
int res = x;
for (auto e : g[v]) {
if (e.to == p) continue;
res += dfs(e.to, x^(e.w & 1), v);
}
return res;
}
mint solve() {
int x = dfs(0);
return mint(n - x) * x;
}
int main() {
cin >> n;
g.resize(n);
rep(i, n - 1) {
int a, b; ll w;
cin >> a >> b >> w;
--a; --b;
g[a].emplace_back(b, w);
g[b].emplace_back(a, w);
}
mint ans, two = 1;
rep(i, 60) {
ans += solve() * two;
rep(v, n)rep(j, g[v].size()) g[v][j].w >>= 1;
two *= 2;
}
cout << ans.val() << '\n';
return 0;
}