树上异或距离(Tree XOR Distance) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<pair<int, long long>>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    vector<long long> xr(n + 1, 0);
    vector<int> p(n + 1, 0), st = {1};
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        for (auto& e : adj[u]) {
            if (e.first != p[u]) {
                p[e.first] = u;
                xr[e.first] = xr[u] ^ e.second;
                st.push_back(e.first);
            }
        }
    }
    const long long MOD = 1000000007LL;
    long long ans = 0;
    for (int b = 0; b < 60; ++b) {
        long long c1 = 0;
        for (int i = 1; i <= n; ++i) {
            if ((xr[i] >> b) & 1LL) ++c1;
        }
        long long c0 = n - c1;
        long long pairs = (c0 % MOD) * (c1 % MOD) % MOD;
        long long weight = (1LL << b) % MOD;
        ans = (ans + pairs * weight) % MOD;
    }
    cout << ans << "\n";
    return 0;
}