题目描述： 有一棵由 n 个节点组成的无向树，以 0 为根节点，节点编号从 0 到 n - 1 。给你一个长度为 n - 1 的二维 整数 数组 edges ，其中 edges[i] = [ai, bi] 表示在树上的节点 ai 和 bi 之间存在一条边。另给你一个下标从 0 开始、长度为 n 的数组 coins 和一个整数 k ，其中 coins[i] 表示节点 i 处的金币数量。
从根节点开始，你必须收集所有金币。要想收集节点上的金币，必须先收集该节点的祖先节点上的金币。
节点 i 上的金币可以用下述方法之一进行收集：
收集所有金币，得到共计 coins[i] - k 点积分。如果 coins[i] - k 是负数，你将会失去 abs(coins[i] - k) 点积分。 收集所有金币，得到共计 floor(coins[i] / 2) 点积分。如果采用这种方法，节点 i 子树中所有节点 j 的金币数 coins[j] 将会减少至 floor(coins[j] / 2) 。 返回收集 所有 树节点的金币之后可以获得的最大积分。
数据范围：
$2 \le n \le 10^5; 0 \le coins[i] \le 10^4; 0 \le k \le 10^4$
题解： 题目看错了，写了个递推的树形dp，结果答案不对。后来才发现采用第二种方法的话，节点 $i$ 子树中的所有节点，不只是直系儿子节点，金币都会减少至 $floor(coins[j] / 2)$ ，也就是所有的节点都要除以 $2$ 。
因为 $0 \le coins[u] \le 10^4$ ，数据范围比较小，可以发现最多除以 $2$ 出现 $14$ 次，以后子树中所有节点的值全是 $0$ 。
可以使用记忆化搜索，记录路径上已经使用了几次方式二，大于等于 $14$ 时直接返回。否则的话对 $u$ 节点枚举使用了方式一还是方式二。
代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 auto optimize_cpp_stdio = [](){ std ::ios::sync_with_stdio(false ); std ::cin .tie(nullptr ); std ::cout .tie(nullptr ); return 0 ; }(); class Solution { public : const static int maxn = 1e5 + 10 ; const static int maxm = 1e5 + 10 ; const int INF = 0x3f3f3f3f ; vector <vector <int >> g; vector <vector <int >> dp; int dfs (int u, int fa, int cnt, vector <int > &coins, int k) { if (cnt >= 14 ) return 0 ; if (dp[u][cnt] != -1 ) return dp[u][cnt]; int tmp1 = floor (coins[u] >> cnt) - k; int tmp2 = floor (coins[u] >> (cnt + 1 )); for (int i = 0 ; i < g[u].size(); ++i) { int v = g[u][i]; if (v == fa) continue ; tmp1 += dfs(v, u, cnt, coins, k); tmp2 += dfs(v, u, cnt + 1 , coins, k); } dp[u][cnt] = max(tmp1, tmp2); return dp[u][cnt]; } int maximumPoints (vector <vector <int >> &edges, vector <int > &coins, int k) { int n = coins.size(); g.resize(n); dp.resize(n, vector <int >(14 , -1 )); for (auto &edge : edges) { int u = edge[0 ]; int v = edge[1 ]; g[u].emplace_back(v); g[v].emplace_back(u); } return dfs(0 , -1 , 0 , coins, k); } };