Source Code
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<vector<vector<int>>> adj[2];
const int N= 1e5 + 10;
int cnt[2][2][N];
int B;
void dfs(int node, int tree, int parity, int parent){
        cnt[tree][parity][0]++;
        for(auto &v : adj[tree][node]){
                int to = v[0];
                int w  = v[1];
                if(to == parent) continue;
                
                int new_parity= parity;
                if(w & (1 << B)) new_parity ^= 1;
                dfs(to, tree, new_parity, node);
        }
}

int ans= 0;
const int MOD = 1e9 + 7;
void reroot(int node, int tree, int parent){
        if(tree == 1){
                ans += (1LL * cnt[0][0][node] * cnt[1][1][node] % MOD +
                        1LL * cnt[0][1][node] * cnt[1][0][node] % MOD) * 1LL * (1 << B) % MOD;
                
                if(ans >= MOD) ans -= MOD;
        }
        
        for(auto &v : adj[tree][node]){
                int to = v[0];
                int w  = v[1];
                if(to == parent) continue;
                
                bool edge= w & (1 << B);
                for(int parity= 0; parity < 2; parity++){
                        cnt[tree][parity][to]= cnt[tree][parity ^ edge][node];
                }
                reroot(to, tree, node);
        }
}

int main(){
        cin.tie(0);
        cin.sync_with_stdio(0);
        
        int n; cin>>n;
        
        for(int p = 0; p < 2; p++){
                adj[p].resize(n);
                for(int i = 0; i + 1 < n; i++){
                        int u, v, w;
                        cin>>u>>v>>w;
                        adj[p][u - 1].push_back({v - 1, w});
                        adj[p][v - 1].push_back({u - 1, w});
                }
        }
        
        for(int bt= 0; bt < 30; bt++){
                B= bt;
                for(int p = 0; p < 2; p++){
                        cnt[p][0][0] = cnt[p][1][0]= 0;
                        dfs(0, p, 0, -1);
                        reroot(0, p, -1);
                }
        }
        cout<<ans<<"\n";
}
Copy
Trees xOr maghrabyJr_
GNU G++17
4276 ms
32.2 MB
Accepted