Source Code
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int N=100005,mod=(1e9)+7;
int dp[2][2][32][N];
vector<vector<pair<int,int>>>adj[2];
void dfs_down(int v,int p,int idx,int bit){
    dp[idx][0][bit][v]=1;
    for(auto&[u,w]:adj[idx][v]){
        if(u==p)continue;
        dfs_down(u,v,idx,bit);
        int cur=(w>>bit)&1;
        dp[idx][0][bit][v]+=dp[idx][cur][bit][u];
        dp[idx][1][bit][v]+=dp[idx][cur^1][bit][u];
    }
}
void dfs_up(int v,int p,int pw,int idx,int bit){
    if(~p){
        dp[idx][0][bit][v]=dp[idx][pw][bit][p];
        dp[idx][1][bit][v]=dp[idx][pw^1][bit][p];
    }
    for(auto&[u,w]:adj[idx][v]){
        if(u==p)continue;
        dfs_up(u,v,(w>>bit)&1,idx,bit);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    adj[0].resize(n);
    adj[1].resize(n);
    for(int k=0;k<2;k++)for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        u--;v--;
        adj[k][u].push_back({v,w});
        adj[k][v].push_back({u,w});
    }
    for(int idx=0;idx<2;idx++)for(int bit=0;bit<30;bit++){
        dfs_down(0,-1,idx,bit);
        dfs_up(0,-1,0,idx,bit);
    }
    long long res=0;
    for(int bit=0;bit<30;bit++)for(int i=0;i<n;i++){
        long long cnt=dp[0][0][bit][i]*1LL*dp[1][1][bit][i];
        cnt+=dp[0][1][bit][i]*1LL*dp[1][0][bit][i];
        cnt%=mod;
        res+=((1LL<<bit)*cnt)%mod;
    }
    cout<<(res%mod);
    return 0;
}

Copy
Trees xOr AbdelmagedNour
GNU G++17
1709 ms
60.2 MB
Accepted