Submission #7991033

---

Source Code Expand

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

struct edge{
	ll to, weight;
};

ll N, X;
vector<ll> d(101010, -1);
vector<edge> G[101010];

void dfs(ll now, ll par, ll dist){
	d[now] = dist;
	REP(i, G[now].size()){
		edge e = G[now][i];
		if(e.to == par) continue;
		dfs(e.to, now, dist^e.weight);
	}
	return;
}

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

    cin >> N >> X;
    REP(i, N-1){
    	ll x, y, c;
    	cin >> x >> y >> c;
    	x--, y--;
    	edge e = {y, c};
    	edge f = {x, c};
    	G[x].push_back(e);
    	G[y].push_back(f);
    }

    dfs(0, -1, 0);

    map<ll, ll> mp;
    REP(i, N) mp[d[i]]++;

    ll res = 0;
    for(auto x: mp){
    	ll val = x.first;
    	if(val == X^val) res += (mp[val] * (mp[val]-1));
    	else res += mp[val] * mp[X^val];
    }
    cout << res/2 << endl;
    return 0;
}

Submission Info

Judge Result