牛客巅峰赛第10场代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ---------------------- "<<endl
#define uint unsigned int
#define ULL unsigned long long
#define DB double
#define LDB long double
#define pii pair<int,int>
#define mpt make_pair
#define pb push_back
#define fr first
#define sc second
#define M 1000020//Size
#define INF 1000000000
#define INFLL 1000000000000000000
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define mod 1000000007//About
inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
inline int mns(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
inline int mul(LL x,LL y){return x*y%mod;}
inline void upd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
inline void dec(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
inline int qpow(int x,LL sq){int res=1;for(;sq;sq>>=1,x=mul(x,x))if(sq&1)res=mul(res,x);return res;}
int n,fa[M],val[M],sz[M],top;
pii e[M];
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型 节点个数
     * @param u int整型vector
     * @param v int整型vector
     * @return int整型
     */
    inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    inline void mrg(int x,int y){
        if(find(x)^find(y)) fa[fa[x]]=fa[y];
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& p) {
        // write code here
        for(int i=1;i<n;i++) e[i]=mpt(u[i-1]+1,v[i-1]+1);
        for(int i=1;i<=n;i++) val[i]=p[i-1];
        LL ans=0ll;
        for(int k=0;k<=20;k++){
            for(int i=1;i<=n;i++) fa[i]=i,sz[i]=0;
            for(int i=1;i<n;i++)
                if((val[e[i].fr]&(1<<k))&&(val[e[i].sc]&(1<<k))){
                    mrg(e[i].fr,e[i].sc);
                }
            LL res=0ll;
            for(int i=1;i<=n;i++) if(val[i]&(1<<k)) res++,sz[find(i)]++;
            for(int i=1;i<=n;i++) if((val[i]&(1<<k))&&find(i)==i) res+=(LL)sz[i]*(sz[i]-1)/2ll;
            ans+=(LL)res*(1ll<<k);
        } return ans;
    }
}t;