Submission #1113712

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int size = 100000;
ll N, X;
ll x[size], y[size], c[size];
vector< pair<ll, ll> > edges[size];

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

bool visited[size];
unordered_map<ll, ll> hashMap;

void makeHashMap() {
  queue< pair<ll, ll> > q;
  
  q.push(make_pair(0, 0));
  hashMap[0] += 1;
  visited[0] = true;
  
  while(q.size()) {
    pair<ll, ll> qfront = q.front();
    q.pop();
    
    ll from = qfront.first;
    ll prevxor = qfront.second;
    
    for(pair<ll, ll> path: edges[from]) {
      if(visited[path.first] == false) {
	visited[path.first] = true;
	
	ll newxor = prevxor ^ path.second;
	q.push( make_pair(path.first, newxor) );
	hashMap[newxor] += 1;
      }
    }
    
  }
  
}

void solve() {
  makeHashMap();

  ll ans = 0;
  
  for(pair<ll, ll> p: hashMap) {
    if(p.first == (p.first ^ X) ) {
      ans += 2 * p.second * hashMap[p.first ^ X];
    }else {
      ans += p.second * hashMap[p.first ^ X];
    }
  }
  
  cout << ans / 2 << endl;
}

int main() {
  init();
  solve();
}

Submission Info

Judge Result