class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n long长整型 老师给牛牛的数字
     * @return int整型
     */
    int mathexp(long long n) {
        // write code here
        while (1){
            long long te=n,nn=te%10;
            te/=10;
            while (te){
                nn*=(te%10);
                te/=10;
            }
            if (nn==n) break;
            n=nn;
        }
        return n;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int f[1100000];
    int wwork(int n, vector<int>& a) {
        // write code here
        int ans=0;
        int mi=n+1;
        for(int i=n-1;i>=0;--i){
            if (mi<a[i]) ++ans;
            if (a[i]<mi) mi=a[i];
        }
        return ans;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @return long长整型
     */
    long long Sum(int n) {
        // write code here
        long long ans=0;
        for(long long i=1;i<=n;i<<=1){
            ans+=n/i*i;
        }
        return ans;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 点的个数
     * @param u int整型vector 每条边的起点
     * @param v int整型vector 每条边的终点
     * @param p int整型vector 每个点的价值
     * @return long长整型
     */
    vector<int> P;
    long long f[110000][21],ans;
    vector<int> e[110000];
    void dfs(int x,int fa){
        for(int y:e[x])if (y!=fa){
            dfs(y,x);
            for(int i=0;i<=20;++i) if (P[x]&(1<<i)){
                f[x][i]+=f[y][i];
                ans-=((f[y][i]*f[y][i])<<i);
            }
        }
        for(int i=0;i<=20;++i){
            if (P[x]&(1<<i)) f[x][i]++;
            ans+=((f[x][i]*f[x][i])<<i);
        }
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& p) {
        P=p;
        for(int i=0;i<u.size();++i){
            e[u[i]].push_back(v[i]);
            e[v[i]].push_back(u[i]);
        }
        dfs(0,-1);
        long long te=0;
        for(int i=0;i<p.size();++i)
            te+=p[i];
        ans=(ans-te)/2+te;
        return ans;
    }
};