节点 i 上的金币可以用下述方法之一进行收集：
收集所有金币，得到共计 coins[i] - k 点积分。如果 coins[i] - k 是负数，你将会失去 abs(coins[i] - k) 点积分。
收集所有金币，得到共计 floor(coins[i] / 2) 点积分。如果采用这种方法，节点 i 子树中所有节点 j 的金币数 coins[j] 将会减少至 floor(coins[j] / 2) 。
返回收集所有树节点的金币之后可以获得的最大积分
1. 动态规划树
由于每个节点有两种选择，导致后面会有重复的状态，采用动态规划
class Solution {
public:
int maximumPoints(vector<vector<int>> &edges, vector<int> &coins, int k) {
int n = coins.size();
vector<vector<int>> g(n);//create graph
for (auto &e: edges) {
int x = e[0], y = e[1];
g[x].push_back(y);
g[y].push_back(x);
}
vector<vector<int>> memo(n, vector<int>(32, INT_MIN)); // 第i个节点位于第j层时子树的最大积分
function<int(int, int, int)> dfs = [&](int i, int j, int fa) -> int {//第i个节点位于第j层时子树的最大积分
auto &res = memo[i][j]; // 注意这里是引用
if (res != INT_MIN) // 之前计算过
return res;
int res1 = (coins[i] >> j) - k;//第一种方法
int res2 = coins[i] >> (j + 1);//第二种方法
for (int ch: g[i]) {//遍历子节点
if (ch == fa) continue;//跳过父节点
res1 += dfs(ch, j, i); // 第一种方法子节点的情况
if(j<30)
res2 += dfs(ch, j + 1, i); // 第二种方法子节点的情况
}
return res = max(res1, res2); // 记忆化
};
return dfs(0, 0, -1);//从根结点开始，深度为0，无前驱
}
};