AtCoder Regular Contest 045 C - エックスオア多橋君
分からなかったので解答を見た。どちらかというと難しいと感じた。
C - エックスオア多橋君
問題
非負整数の重みが付いた木が与えられる。この木の上の長さが$1$以上の道で、道上の重みの排他的論理和による総和が$x$であるものの数を答えよ。
解説
排他的論理和の性質を使う。 根から頂点$a,b$への重みの排他的論理和を取ると、ふたつの道の共通部分が打ち消しあい、頂点$a,b$間の道の重みが得られる。
適当に決めた根から、全ての頂点への道を考え、その重みを数えるのは$O(n)$。 重みのそれぞれに関して、排他的論理和を取って$X$になるような重みを見つけるのは、$a \oplus b = x \iff a \oplus x = b$と変形すれば$O(\log n)$。
$O(n \log n)$。
実装
長さ$0$の道は許されていないのに注意。
#include <iostream>
#include <vector>
#include <map>
#include <cstdint>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
typedef long long ll;
using namespace std;
struct edge_t { int to; uint32_t cost; };
void dfs(int v, int p, uint32_t value, vector<vector<edge_t> > const & g, map<uint32_t,ll> & acc) {
acc[value] += 1;
for (auto e : g[v]) if (e.to != p) {
dfs(e.to, v, value ^ e.cost, g, acc);
}
}
int main() {
int n; uint32_t x; cin >> n >> x;
vector<vector<edge_t> > g(n);
repeat (i,n-1) {
int x, y; uint32_t c; cin >> x >> y >> c;
-- x; -- y;
g[x].push_back((edge_t){ y, c });
g[y].push_back((edge_t){ x, c });
}
map<uint32_t,ll> acc;
dfs(0, -1, 0, g, acc);
ll result = 0;
for (auto it : acc) {
if (it.first < (it.first ^ x)) {
result += acc[it.first ^ x] * it.second;
} else if (it.first == (it.first ^ x)) { // means x == 0
result += it.second * (it.second - 1) / 2;
}
}
cout << result << endl;
return 0;
}