Submission #2549399

---

Source Code Expand

#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

struct Edge {
  int to, c;
};

int main() {
  int N, X;
  while (cin >> N >> X) {
    vector<vector<Edge>> G(N);
    for (int i = 0; i < N - 1; i++) {
      int x, y, c;
      cin >> x >> y >> c;
      --x;
      --y;
      G[x].push_back(Edge{y, c});
      G[y].push_back(Edge{x, c});
    }
    vector<int> xsum(N);
    function<void(int, int, int)> dfs = [&](int v, int p, int c) {
      xsum[v] = c;
      for (auto& e : G[v]) {
        if (e.to == p) continue;
        dfs(e.to, v, c ^ e.c);
      }
    };
    dfs(0, -1, 0);
    map<int, int> cnt;
    for (int x : xsum) ++cnt[x];
    ll res = 0;
    for (int i = 0; i < N; i++) {
      int y = X ^ xsum[i];
      if (y == xsum[i]) {
        res += cnt[y] - 1;
      } else {
        res += cnt[y];
      }
    }
    res /= 2;
    cout << res << endl;
  }
  return 0;
}

Submission Info

Judge Result