E - Xor Distances Editorial by MMNMM


ビットごとに考えます。 解くべき問題は次のようになります。

辺の長さが \(0\) または \(1\) である木が与えられる。\(i,j\) の間の最短距離が奇数であるような頂点の組 \((i,j)\ (1\leq i<j\leq N)\) の個数はいくつか。

与えられるグラフが木であることから、頂点の集合 \(V\)\(V_0,V_1\) に分け(正確な表現をすれば、「\(V_0\cup V_1=V, V_0\cap V_1=\varnothing\) を満たすような \(V_0,V_1\) を取り」)、

  • \(i\in V_0, j\in V_1\) または \(i\in V_1, j\in V_0\iff \operatorname{dist}(i,j)\) が奇数

が成り立つようにすることができます。 これは、二部グラフ性の判定などと同様に適当な頂点から貪欲に色を塗っていくことで実現できます。
つまり、ある頂点を黒で塗ったならば、その頂点と長さ \(0\) の辺で結ばれている頂点は黒、長さ \(1\) の辺で結ばれている頂点は白で塗る ようにすればよいです。

このような \(V\) の分割 \(V_0,V_1\) がとれたとき、答えは \(|V_0|\times|V_1|\) と求められます。
これを各ビットに対して行ったのち、適当な係数をかけて足すことで答えを求めることができます。
色を塗り、\(|V_0|\) などを更新していくことを全てのビットに対して同時に行うと、想定解と同じ処理になります。

以下はC++でのACコードです。

#include<bits/stdc++.h>

int main(){
    using namespace std;
    constexpr unsigned long MOD{1000000007};
    unsigned long N;
    cin >> N;
    vector<vector<pair<unsigned long, unsigned long>>> edge(N);
    for(unsigned long i{1}, a, b, w; i < N; ++i){
        cin >> a >> b >> w;
        edge[--a].emplace_back(--b, w);
        edge[b].emplace_back(a, w);
    }

    vector<unsigned long> cnt(60);
    [dfs_impl = [&cnt, &edge](auto&& f, unsigned long now, unsigned long prev, unsigned long x) -> void {
        for(unsigned long i{}; i < 60; ++i)if(x & (1UL << i))++cnt[i];
        for(const auto& [next, w] : edge[now])if(next != prev)f(f, next, now, x ^ w);
    }]{dfs_impl(dfs_impl, 0, 0, 0);}();

    unsigned long ans{};
    for(unsigned long i{60}; i--; )((ans *= 2) %= MOD) += cnt[i] * (N - cnt[i]);
    cout << ans % MOD << endl;

    return 0;
}

posted:
last update: