提出 #813534

---

ソースコード 拡げる

#include <string>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <unordered_map>
#include <algorithm>

struct Node {
  std::vector<int> to;
  std::vector<std::size_t> cost;
  bool done = false;
};

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

  std::string line;
  std::getline(std::cin, line);

  char * p;
  int N = std::strtol(line.data(), &p, 10);
  std::size_t X = std::strtol(p, NULL, 10);

  std::vector<Node> node(N);
  for (int i = 0; i < N - 1; ++i) {
    std::getline(std::cin, line);
    int s = std::strtol(line.data(), &p, 10) - 1;
    int e = std::strtol(p, &p, 10) - 1;
    std::size_t x = std::strtoll(p, &p, 10);
    node[s].to.push_back(e);
    node[s].cost.push_back(x);
    node[e].to.push_back(s);
    node[e].cost.push_back(x);
  }

  int root = 0;
  for (int i = 0; i < N; ++i) {
    if (node[i].to.size() == 1) {
      root = i;
      break;
    }
  }

  std::vector<std::size_t> value(N, 0);
  std::vector<int> stack;
  stack.reserve(N / 4);

  stack.push_back(root);
  while (stack.size() > 0) {
    int i = stack.back();
    stack.pop_back();
    for (int j = 0; j < node[i].to.size(); ++j) {
      int k = node[i].to[j];
      if (!node[k].done) {
        value[k] = value[i] ^ node[i].cost[j];
        stack.push_back(k);
      }
    }
    node[i].done = true;
  }

  std::sort(value.begin(), value.end());
  std::unordered_map<std::size_t, int> unique;

  auto first = value.begin();
  auto last = value.end();

  for (;first < last; ++first) {
    unique[*first] += 1;
  }

  int ret = 0;
  if (X == 0) {
    for (auto const & p : unique) {
      if (p.second >= 1) {
        int n = 2 * p.second;
        ret += n * (n - 1) / 2;
      }
    }
    std::cout << ret / 2 << std::endl;
    return 0;
  }

  for (auto first = unique.begin(), last = unique.end(); first != last; ++first) {
    std::size_t x1 = first->first;
    std::size_t x2 = (X ^ x1);
    auto it = unique.find(x2);
    if (it != unique.end()) {
      ret += first->second * it->second;
    }
  }

  std::cout << (ret / 2) << std::endl;
}

提出情報

ジャッジ結果