C++14(g++5.4) 解法, 执行用时: 35ms, 内存消耗: 2376K, 提交时间: 2020-09-09 19:25:49

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n,d[N],cnt[40]; long long res;
int head[N],nex[N],to[N],w[N],tot;
inline void add(int a,int b,int c){
    to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
void dfs(int x,int dis){
    d[x]=dis;
    for(int i=head[x];i;i=nex[i])   dfs(to[i],w[i]^dis);
    for(int i=20;i>=0;i--)   if(dis>>i&1)  cnt[i]++;
}
signed main(){
    cin>>n;
    for(int i=2,a,b;i<=n;i++)    scanf("%d %d",&a,&b),add(a,i,b);
    dfs(1,0);
    for(int i=0;i<=20;i++)   res=(res+(1LL<<i)*1LL*cnt[i]%mod*(n-cnt[i])%mod)%mod;
    cout<<(res*2)%mod;
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 93ms, 内存消耗: 2384K, 提交时间: 2023-04-17 09:54:04

#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=1e5+10,M=N,mod=1e9+7;
int h[N],e[M],ne[M],w[M],idx;
int f[N],cnt[N];
int n;
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs(int u)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
		f[j]=f[u]^w[i];
        dfs(j);
    }
    for(int i=0;i<31;i++)if(f[u]>>i&1)cnt[i]++;
}
signed main()
{
    memset(h,-1,sizeof(h));
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        int p,w;
        cin>>p>>w;
        add(p,i,w);
    }
    dfs(1);
    int ans=0;
    for(int i=0;i<31;i++)ans=(ans+(1ll<<(i+1))*cnt[i]%mod*(n-cnt[i])%mod)%mod;
    cout<<ans;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 67ms, 内存消耗: 1156K, 提交时间: 2020-08-03 14:56:01

#include <iostream>
#include <algorithm>
#include <cstring>

#define int long long

using namespace std;

const int maxn=1e5+5,mod=1000000007;

int n,v[maxn],num[maxn];

signed main()
{
    cin>>n;
    for(int i=1;i<n;i++){
        int fa,val;
        cin>>fa>>val;
        v[i+1]=v[fa]^val;
     //   cout<<v[i+1]<<endl;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<31;j++){
            if(v[i]&(1<<j)) num[j+1]++;
        }
    }
    int res=0;
    for(int i=0;i<31;i++) res=(res+((1<<i)*num[i]%mod*(n-num[i])%mod))%mod;
    cout<<res<<endl;
    return 0;
}