leetcode 2920. 收集所有金币可获得的最大积分

题目：2920. 收集所有金币可获得的最大积分 - 力扣（LeetCode）

看数据范围是需要O(n*log(n))的算法。可以用dfs+记忆化搜索。

考虑到coins[i]的范围是[0, 10000]，最多除个十几次2就变成0了。所以用w[i][j]表述节点i在除以j次后，以i为根节点的子树的最大值，来进行dfs的记忆化。

struct Node {
    vector<Node*> links;
    vector<Node*> children;
    int idx;
    int* val = new int[16];
    int* w = new int[16];
    bool* f = new bool[16];
    Node(int idx, int v) {
        this->idx = idx;
        memset(f, 0, 16);
        val[0] = v;
        for (int i = 1; i < 16; i++) {
            val[i] = val[i - 1] / 2;
        }
    }
    void Build(int parent = -1) {
        for (int i = 0; i < links.size(); i++) {
            if (links[i]->idx != parent) {
                children.push_back(links[i]);
                links[i]->Build(idx);
            }
        }
    }
    int DFS(int t, int k) {
        if (t >= 16) {
            return 0;
        }
        if (f[t]) {
            return w[t];
        }
        int a = (t < 16 ? val[t] : 0) - k;
        for (int i = 0; i < children.size(); i++) {
            a += children[i]->DFS(t, k);
        }
        int b = t < 15 ? val[t + 1] : 0;
        for (int i = 0; i < children.size(); i++) {
            b += children[i]->DFS(t + 1, k);
        }
        f[t] = true;
        w[t] = max(a, b);
        return w[t];
    }
};
class Solution {
public:
    int maximumPoints(vector<vector<int>>& edges, vector<int>& coins, int k) {
        vector<Node*> tree;
        for (int i = 0; i < coins.size(); i++) {
            tree.push_back(new Node(i, coins[i]));
        }
        int a, b;
        for (int i = 0; i < edges.size(); i++) {
            a = edges[i][0];
            b = edges[i][1];
            tree[a]->links.push_back(tree[b]);
            tree[b]->links.push_back(tree[a]);
        }
        tree[0]->Build();
        
        return tree[0]->DFS(0, k);
    }
};