AtCoder Regular Contest 045 C - エックスオア多橋君

ARC 045 に参加しました。途中まで B も解けなくて死ぬかと思いましたがなんとか C まで解けました。

問題

arc045.contest.atcoder.jp

解法

xor の特徴からして, 頂点 v から 頂点 u までのパスにおける xor 和 = (頂点 0 から v までの xor 和) xor (頂点 0 から u までの xor 和) となります。この観察が一番重要です。

頂点 0 から 頂点 v までの xor 和 を cost[v] とします。
頂点 v から どこの頂点までの パスを使えば目標値 X になるかというのは, cost[v] ^ X が cost[u] になる u の数を求めれば良いです。これは, 最初に前処理しておくことで大体 O(1) で求められます(僕は map を使ったので O(1) ではないですが)。

const int MAXN = 100100;
vector<pii> G[MAXN];
int cost[MAXN];
map<int, int> M;

void dfs(int v, int p, int now) {
    cost[v] = now;
    M[now]++;
    for (auto ch : G[v]) {
        int tmp = ch.first;
        if (tmp == p) continue;
        dfs(tmp, v, now^ch.second);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, X;
    cin >> N >> X;
    for (int i = 0; i < N-1; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        x--, y--;
        G[x].emplace_back(y, c);
        G[y].emplace_back(x, c);
    }
    dfs(0, -1, 0);
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        int tar = cost[i]^X;
        if (tar != cost[i]) ans += M[tar];
        else ans += M[tar]-1;
    }
    cout << ans/2 << endl;
    return 0;
}