牛牛的路径和

牛牛的路径和

思路：

要求计算二进制按位与下的结果， 在二进制下只有连续的1会有值， 所以记录点权二进制下的0/1信息，树形dp求值，树形dp求值（好笼统呀):
即当前节点可以产生的贡献就是当前结点第i为上连续1的数量与其儿子第i为连续1的数量乘积 乘对应位置的值(即1<<i)的和
好乱 每个结点单独也算贡献。

代码展示

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 1e5 + 7;

typedef long long LL;
LL dp[maxn][22];
vector<int> G[maxn];
int w[maxn];
LL ans;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 点的个数
     * @param u int整型vector 每条边的起点
     * @param v int整型vector 每条边的终点
     * @param p int整型vector 每个点的价值
     * @return long长整型
     */

    void dfs(int u, int f){

        for (int i = 0; i <= 20; i ++ ){
            if (w[u] >> i & 1) dp[u][i] = 1;
            else dp[u][i] = 0;
        }
        ans += w[u];
        for (int i = 0; i < G[u].size(); i ++ ){
            int v = G[u][i];
            if (v == f) continue;
            dfs(v, u);
            for (int j = 0; j <= 20; j ++ ){
                ans += dp[u][j] * dp[v][j] * (1ll << j);//
                if (w[u] >> j & 1) dp[u][j] += dp[v][j];
            }

        }
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& p) {
        // write code here
        ans = 0;
        for (int i = 0; i < n - 1; i ++ ){
            G[u[i]].push_back(v[i]);
            G[v[i]].push_back(u[i]);
        }
        for (int i = 0; i < n; i ++ ) w[i] = p[i];
        dfs(1, -1);
        return ans;
    }
};