AT_abc201_e [ABC201E] Xor Distances 题解

CD_Sun_doer · 2024-11-18 20:17:01 · 题解

题目大意：

给定一颗带边权无根树，定义 dis(i,j) 表示 i,j 两点在树上的最短路径中所有边权异或的值。求：

思路：

首先明确一点，即：

因为两者的公共部分由于异或而抵消了。

那我们可以先预处理出来根节点到每一个节点的权值，即 dis(i,j)。接着我们按位考虑，假设第 k 位的某一段有贡献，那只可能是 1，那要得到这个贡献必须是 0 \oplus 1。我们要求所有有贡献的段，考虑如何计算，先统计 1 的个数设为 cnt，cnt=\sum_{i=1}^{n} (dis(root,i) \gg k) \& 1 ，则 0 的个数为 n-cnt 那可以产生贡献的段的贡献和即为 cnt \times (n-cnt)，别忘了我们每次只枚举第 k 位，所以最终：

即为所求。另注意取模。

代码：

#include<bits/stdc++.h>
#define int long long
#define Up(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int N=2e5+10,mod=1e9+7;
int n,ans;
struct Edge{
    int v,w;
};
vector<Edge> e[N];
int d[N];
void dfs(int u,int fa){
    for(auto it:e[u]){
        if(it.v==fa) continue;
        d[it.v]=d[u]^it.w;
        dfs(it.v,u);
    }
}
signed main(){
    cin.tie(0),cout.tie(0)->sync_with_stdio(0);
    cin>>n;
    Up(i,1,n-1){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    d[1]=0;
    dfs(1,0);
    Up(k,0,60){
        int cnt=0;
        Up(i,1,n) cnt+=((d[i]>>k)&1ll);
        cnt%=mod;
        ans+=((1ll<<k)%mod)*(cnt*(n-cnt)%mod)%mod;
        ans%=mod;
    }
    cout<<ans<<"\n";
    return 0;
}