ARC45 C問題 エックスオア多橋くん

久しぶりに問題解いた気がする。
a xor b = cのとき、a xor c = bであることを使うとまぁ簡単にいく。
と思いきや、オーバーフローで2つほど落ちてた。はぁ。

vector<P> G[100001];
map<ll, ll> mp;

void dfs(int now, int pre, int cost)
{
    mp[cost]++;
    for(auto v : G[now]){
        if(v.first != pre){
            dfs(v.first, now, cost^v.second);
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

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

    ll res = 0;
    for(auto it=mp.begin(); it!=mp.end(); it++){
        ll tar = X^it->first;
        if(it->first == tar){
            res += it->second*(it->second-1)/2;
        }else{
            if(it->first < tar) res += it->second*mp[tar];
        }
    }
    cout << res << endl;
}