题解 | #整除问题#

const int M = 1e5+7;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型 点的个数
     * @param u int整型vector 每条边的起点
     * @param v int整型vector 每条边的终点
     * @param p int整型vector 每个点的价值
     * @return long长整型
     */
 
    int head[M],cnt=1;
void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
int a[M],vs[M];
long long nm;
void dfs(int x){
    vs[x]=1;
    nm++;
    for(int i=head[x];i;i=ee[i].nxt){
        int y=ee[i].to;
        if(vs[y]||a[y]==0)continue;
        dfs(y);
    }
}
long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& p) {
        // write code here
        init(n);
        for(int i=0;i<n-1;i++){
            a[i]=p[i];
            add(u[i],v[i],1);
            add(v[i],u[i],1);
        }
        long long ans=0;
        for(int sta=0;sta<=20;sta++){
            for(int i=0;i<n;i++)if((p[i]>>sta)&1)a[i]=1;else a[i]=0;
            memset(vs,0,sizeof(vs));
            for(int i=0;i<n;i++){
                if(vs[i]||a[i]==0)continue;
                nm=0;
                dfs(i);
                ans+=(nm+nm*(nm-1)/2)*(1<<sta);
            }
        }
        return ans;
    }
};