第 369 场周赛(简单位运算，分类讨论，dfs，树形dp)

class Solution {
public:
    int findKOr(vector<int>& nums, int k) {
        vector<int> bit(32, 0);
        for(int i = 0; i < 31; i ++ ) {
            int cnt = 0;
            for(auto x: nums) {
                if(x >> i & 1) cnt ++ ;
            }
            if(cnt >= k) bit[i] = 1;
        }
        
        int res = 0;
        for(int i = 0; i < 31; i ++ ) {
            if(bit[i]) res += 1 << i;
        }
        
        return res;
    }
};

class Solution {
public:
    long long minSum(vector<int>& nums1, vector<int>& nums2) {
        long long sum1 = 0, sum2 = 0;
        int cnt1 = 0, cnt2 = 0;
        
        for(auto x: nums1) {
            sum1 += x;
            if(x == 0) cnt1 ++ ;
        }
        
        for(auto x: nums2) {
            sum2 += x;
            if(x == 0) cnt2 ++ ;
        }
        
        
        if(sum1 > sum2) {
            if(sum2 + cnt2 > sum1 && cnt1 == 0 || cnt2 == 0) return -1;
            return max(sum1 + cnt1, sum2 + cnt2);
        } else if(sum1 < sum2){
            if(sum1 + cnt1 > sum2 && cnt2 == 0|| cnt1 == 0) return -1;
           return max(sum1 + cnt1, sum2 + cnt2);
        } else {
            if(cnt1 == cnt2) return sum1 + cnt1;
            if(cnt1 == 0 || cnt2 == 0) return -1;
            return sum1 + max(cnt1, cnt2);
        }
        
    }
};

class Solution:
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [0] * n
        for i in range(3):
            f[i] = max(0, k-nums[i])
        for i in range(3, n):
            f[i] = min(f[i-3:i]) + max(0, k-nums[i])
        return min(f[-3:])

class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        n = len(coins)
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
            
        @cache
        def dfs(u, fa, time):
            if time > 15:
                return 0
　　　　　　  # 方案1
            res1 = (coins[u] >> time) - k
            for x in g[u]:
                if x != fa:
                    res1 += dfs(x, u, time)
            # 方案2
            time += 1
            res2 = (coins[u] >> time)
            for x in g[u]:
                if x != fa:
                    res2 += dfs(x, u, time)
　　　　　　　 # 两个方案取得最大值
            return max(res1, res2)
        
        return dfs(0, -1, 0)

const int K = 20;

class Solution {
public:
    int maximumPoints(vector<vector<int>>& edges, vector<int>& val, int m) {
        int n = edges.size() + 1;
        vector<vector<int>> a(n);
        for (auto& e : edges) {
            int x = e[0], y = e[1];
            a[x].push_back(y);
            a[y].push_back(x);
        }
        vector<vector<int>> dp(n, vector<int>(K, -1));
        function<int(int, int, int)> solve = [&](int u, int parent, int k) {
            int& ret = dp[u][k];
            if (ret >= 0) return ret;
            ret = 0;
            // 方案1
            int cur = (val[u] >> k) - m;
            for (auto& v : a[u]) {
                if (v == parent) continue;
                cur += solve(v, u, k);
            }
            ret = max(ret, cur);
            //方案2
            if (k + 1 < K) {
                int cur = val[u] >> (k + 1);
                for (auto& v : a[u]) {
                    if (v == parent) continue;
                    cur += solve(v, u, k + 1);
                }
                ret = max(ret, cur);
            }
            return ret;
        };
        int ret = solve(0, -1, 0);
        return ret;
    }
};