题目：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);}
};