C++(clang++11) 解法, 执行用时: 90ms, 内存消耗: 7644K, 提交时间: 2020-12-18 23:02:48

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
typedef long long ll;
class Solution {
public:
	int fa[maxn],size[maxn];
	ll ans=0,tmp;
	int find(int x) {
		return x==fa[x]?x:(fa[x]=find(fa[x]));
	}
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& p) {
        for(int i=0;i<=20;++i) {
        	for(int j=0;j<n;++j) fa[j]=j,size[j]=0;
        	
        	for(int j=0;j<n-1;++j) {
        		if( (p[u[j]]>>i&1)&&(p[v[j]]>>i&1) )
        			fa[find(u[j])]=find(v[j]);
			}
			
			for(int j=0;j<n;++j) size[find(j)]+=1;
			
			tmp=1<<i;
			for(int j=0;j<n;++j) if(fa[j]==j) {
				if(p[j]>>i&1)
				ans+=(size[j]+1)*size[j]/2*tmp;
			}
		}
		return ans;
    }
};

Go(1.14.4) 解法, 执行用时: 142ms, 内存消耗: 18156K, 提交时间: 2020-12-18 21:00:44

package main

// github.com/EndlessCheng/codeforces-go
func solve(n int, x, y, a []int) (s int64) {
	g := make([][]int, n)
	for i, v := range x {
		w := y[i]
		g[v] = append(g[v], w)
		g[w] = append(g[w], v)
	}
	for i := 0; i < 21; i++ {
		c := 0
		var f func(int, int) int
		f = func(v, p int) int {
			one := a[v] >> i & 1
			c += one
			for _, w := range g[v] {
				if w != p {
					o := f(w, v)
					if one > 0 {
						c += one * o
						one += o
					}
				}
			}
			return one
		}
		f(0, n)
		s += 1 << i * int64(c)
	}
	return
}