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

問題

　 $N$ 頂点の木が与えられる。各辺に非負整数のコストがついているとき、頂点 $a$ と $b$ を結ぶ単純パスにおいて通る辺のコストを全てxor取っていったものがある整数 $X$ になるような $(a, b)$ の組み合わせが何通りあるか求めよ。

解法

　ある頂点 $x$ を根と決めたとき、 $a \to b$ という単純パスと $a \to x \to b$ というパスでは通る辺のコストのxorを取っていった値は等しくなる。なぜなら $a \to b$ という単純パスがもともと頂点 $x$ を含むなら自明であるし、含まないときは $x$ から見て $a,b$ の近い方へは往復することになるが、xorなので打ち消すことになるからである。

　よって結局頂点 $x:$ から見たxorの値に関して、その値となるパスが何個存在するかを数えていけばいい。そして現在のパスに関してxorの値が $v$ ならば $X xor v$ となるパスの個数を答えに加算していけば $O(N\log{N})$ でこの問題が解ける。

反省

　1時間10分(2WA)でAC。今見ている頂点から先で得られるxor値の個数を数えて伝播させる方法で解けると思って提出したがこれは $O(N^2)$ かかるものでありTLEだった。結局1時間過ぎてしまい、違う解法が思い浮かぶ気がしなかったので解説スライドを見たが、発想としては近そうで遠いものだった。xorの性質を上手く使えていないのでもっとそこに注意を向けるべきだった。

　別解として書いてある「データ構造をマージする一般的なテク」とやらを調べて、なんか使えそうな気がしたのでTLE解の方をいろいろいじってやってみたが答えが合わず断念。しかしこれは知っておく価値が大きそうなテクニックだ。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N, X;
struct Edge {
    ll to, cost;
};
vector<vector<Edge>> edges;
ll ans = 0;
map<ll, ll> mp;

void dfs(ll curr, ll pre, ll value) {
    ans += mp[value ^ X];
    mp[value]++;
    for (Edge e : edges[curr]) {
        if (e.to == pre) {
            continue;
        }

        dfs(e.to, curr, value ^ e.cost);
    }
}

int main() {
    cin >> N >> X;
    edges.resize(N + 1);
    for (ll i = 0; i < N - 1; i++) {
        ll x, y, c;
        cin >> x >> y >> c;
        edges[x].push_back({ y, c });
        edges[y].push_back({ x, c });
    }

    dfs(1, -1, 0);
    cout << ans << endl;
}