Source Code
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define all(v) v.begin(), v.end()
#define pb push_back
#define sz(x) (int)(x).size()

#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
  cout << vars << " = ";
  string delim = "";
  (..., (cout << delim << values, delim = ", "));
  cout << '\n';
}

template<int MOD>
struct Integral {
  int v_ = 0;

  Integral(int v) : v_(norm(v)) {}
  Integral(long long v) : v_(norm(v)) {}
  Integral(unsigned int v) : v_(norm(v)) {}
  Integral(unsigned long long v) : v_(norm(v)) {}
  Integral() = default;
  ~Integral() = default;
 
  template<typename T> T norm(T v) const {
    if constexpr(sizeof(T) > sizeof(MOD)) {
      v %= MOD;
      if (v < 0) v += MOD;
    } else {
      if (v >= MOD) v -= MOD;
      if (v < 0) v += MOD;
      if (v >= MOD || v < 0) {
        v %= MOD;
        if (v < 0) v += MOD;
      }
    }
    return v;
  }
 
  int val() const { return v_; }
  Integral& operator+=(const Integral& rhs) { v_ += rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
  Integral& operator-=(const Integral& rhs) { v_ += MOD - rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
  Integral& operator*=(const Integral& rhs) { v_ = v_ * 1LL * rhs.val() % MOD; return *this; }
  Integral& operator/=(const Integral& rhs) { v_ = v_ * 1LL * rhs.inv().val() % MOD; return *this; }
  Integral operator+(const Integral& rhs) const { Integral ret = *this; return ret += rhs; }
  Integral operator-(const Integral& rhs) const { Integral ret = *this; return ret -= rhs; }
  Integral operator*(const Integral& rhs) const { Integral ret = *this; return ret *= rhs; }
  Integral operator/(const Integral& rhs) const { Integral ret = *this; return ret /= rhs; }
  bool operator==(const Integral& rhs) const { return val() == rhs.val(); }
  bool operator!=(const Integral& rhs) const { return !(*this == rhs); }
  const Integral operator-() const { return Integral(-val()); }
  const Integral& operator++() { v_ += 1; if (v_ >= MOD) v_ -= MOD; return *this; }
  const Integral operator++(int) { Integral ret = *this; ++(*this); return ret; }
  const Integral& operator--() { v_ += MOD - 1; if (v_ >= MOD) v_ -= MOD; return *this; }
  const Integral operator--(int) { Integral ret = *this; --(*this); return ret; }
 
  Integral power(long long b) const {
    long long ret = 1 % MOD, a = v_;
    for ( ; b; b >>= 1, a = a * a % MOD) if (b & 1) ret = ret * a % MOD; return ret;
  }
  Integral inv() const { return power(MOD - 2); }
 
  std::string to_string() const { return std::string("{") + std::to_string(val()) + "}"; }
};

const int MOD = 1e9 + 7;
using Mint = Integral<MOD>;


inline void solve() {
  int n;
  cin >> n;
  vector<vector<pii>> g(n), g2(n);
  for(int i = 0; i < n - 1; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    g[u].pb({v, w});
    g[v].pb({u, w});
  }
  for(int i = 0; i < n - 1; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    g2[u].pb({v, w});
    g2[v].pb({u, w});
  }
  auto bfs = [&](const vector<vector<pii>> &g) {
    queue<int> q;
    vi dis(n, -1);
    q.push(0);
    dis[0] = 0;
    while(sz(q)) {
      int u = q.front();
      q.pop();
      for(auto [v, c] : g[u]) {
        if(dis[v] == -1) {
          dis[v] = dis[u] ^ c;
          q.push(v);
        }
      }
    }
    return dis;
  };
  auto d1 = bfs(g);
  auto d2 = bfs(g2);
  Mint ans = 0;
  for(int bit = 0; bit < 30; ++bit) {
    vi c1(2), c2(2);
    for(int i = 0; i < n; ++i) {
      ++c1[(d1[i] >> bit & 1)];
      ++c2[(d2[i] >> bit & 1)];
    }
    for(int j = 0; j < n; ++j) {
      Mint cur = 0;
      int b1 = d1[j] >> bit & 1;
      int b2 = d2[j] >> bit & 1;
      if(b1 == b2) {
        cur = Mint(c1[1]) * c2[0];
        cur += Mint(c1[0]) * c2[1];
      } else if(b1 != b2) {
        cur = Mint(c1[1]) * c2[1];
        cur += Mint(c1[0]) * c2[0];
      }
      ans += cur * (1 << bit);
    }
  }
  cout << ans.val() << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  // freopen("input.txt", "r", stdin);
  int T = 1;
  // cin >> T;
  while(T--) {
    solve();
  }
}
Copy
Trees xOr noomaK
GNU G++17
277 ms
13.4 MB
Accepted