AtCoder Beginner Contest 201E

ABC201E

距離の定義に XOR が用いられている． 桁毎に独立して計算して，集計するのが良さそう．

Tree であることを用いると，根からの距離を用いて \(i , j \in N\) 間の距離が求まる． ここで，距離は XOR であることに注意する． \(l \in N\) を \(i,j\) の LCA とおくと， \[\begin{matrix} d_{i,j} &=& d_{i,l} \oplus d_{l,0} \oplus d_{0,l} \oplus d_{l,j} \\ &=& d_{0,i} \oplus d_{0,j} \end{matrix}\] が成り立つ． よって，この式の \(k \in 60\) 桁目が \(1\) かどうかを判定できれば良い．
\(d_{0,i} , i \in N\) の \(k\) 桁目たちの中で， \(1\) になる個数を \(a\), \(0\) になる個数を \(b\) とおく． 2つの XOR で\(1\)を作りたいので， \(0 \oplus 1, 1 \oplus 0\) の2通り． \(i,j \) の選び方で重複しているので /2. \(0\)の選び方と\(1\)の選び方が \(b * a\)通り．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n,m; cin >> n; m = n-1;

  vector<vector<pll>> to(n);

  rep(i,m){

    ll c, a, b; cin >> a >> b >> c;

    --a, --b;

    to[a].emplace_back(b, c);

    to[b].emplace_back(a, c);

  }

  vll v(n);

  auto dfs = [&](auto f, ll cu, ll pa) -> void {

    for(auto [ne, co] : to[cu]) if(ne != pa){

      v[ne] ^= (v[cu] ^ co);

      f(f, ne, cu);

    }

  };

  dfs(dfs, 0, -1);

  mint ans = 0;

  rep(k,60){

    ll one = 0;

    rep(i,n) {

      one += v[i] >> k & 1;

    }

    ll zero = n - one;

    ll p = one*zero;

    ans += mint(1LL << k)*mint(p);

  }

 

  cout << ans.val() << endl;

  return 0;

}