Hard

题目描述

存在一个以节点 0 为根的 n 个节点的无向树，节点标记为 0 到 n - 1。给定一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。还给定一个大小为 n 的 0 索引数组 coins，其中 coins[i] 表示顶点 i 中的硬币数量，以及一个整数 k。

从根节点开始，你必须收集所有硬币，使得只有在已经收集了节点祖先的硬币后，才能收集该节点的硬币。

节点 i 的硬币可以通过以下方式之一收集：

  1. 收集所有硬币，但你将获得 coins[i] - k 分。如果 coins[i] - k 为负数，则你将失去 abs(coins[i] - k) 分。
  2. 收集所有硬币，但你将获得 floor(coins[i] / 2) 分。如果使用这种方式，那么对于节点 i 子树中存在的所有节点 j，coins[j] 将减少到 floor(coins[j] / 2)。

返回从所有树节点收集硬币后可以获得的最大分数。

示例 1：

输入：edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
输出：11
解释：
使用第一种方式从节点 0 收集所有硬币。总分 = 10 - 5 = 5。
使用第一种方式从节点 1 收集所有硬币。总分 = 5 + (10 - 5) = 10。
使用第二种方式从节点 2 收集所有硬币，所以节点 3 剩余的硬币为 floor(3 / 2) = 1。总分 = 10 + floor(3 / 2) = 11。
使用第二种方式从节点 3 收集所有硬币。总分 = 11 + floor(1 / 2) = 11。
可以证明从所有节点收集硬币后能获得的最大分数是 11。

示例 2：

输入：edges = [[0,1],[0,2]], coins = [8,4,4], k = 0
输出：16
解释：
所有节点的硬币都使用第一种方式收集。因此，总分 = (8 - 0) + (4 - 0) + (4 - 0) = 16。

提示：

  • n == coins.length
  • 2 <= n <= 10^5
  • 0 <= coins[i] <= 10^4
  • edges.length == n - 1
  • 0 <= edges[i][0], edges[i][1] < n
  • 0 <= k <= 10^4

解题思路

这是一个经典的树形动态规划问题。关键在于理解两种收集方式的影响：

核心思路：

  1. 状态定义：设 dp[x][t] 表示从节点 x 的子树中能获得的最大分数，其中 t 表示该节点的祖先中使用第二种方式（除以2）的次数。

  2. 状态转移：对于每个节点，我们有两种选择：

    • 使用第一种方式：获得 (coins[x] >> t) - k 分，子节点的除以2次数保持为 t
    • 使用第二种方式：获得 (coins[x] >> (t+1)) 分，子节点的除以2次数变为 t+1

  3. 剪枝优化：当 t >= 14 时，由于 coins[i] <= 10^4，此时 coins[i] >> 14 必定为 0，可以直接返回 0。

  4. 记忆化搜索：使用记忆化避免重复计算，提高效率。

状态转移方程：

dp[x][t] = max(
    (coins[x] >> t) - k + sum(dp[child][t]),
    (coins[x] >> (t+1)) + sum(dp[child][t+1])
)

## 代码实现

<div class="codetabs-container" id="codetabs-1">
  <div class="codetabs-content">
    
<div class="codetab-panel" data-tab-name="C&#43;&#43;">
  <div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="line"><span class="cl"><span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl"><span class="k">public</span><span class="o">:</span>
</span></span><span class="line"><span class="cl">    <span class="n">vector</span><span class="o">&lt;</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&gt;</span> <span class="n">graph</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    <span class="n">vector</span><span class="o">&lt;</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&gt;</span> <span class="n">memo</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">coins</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    <span class="kt">int</span> <span class="n">k</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    
</span></span><span class="line"><span class="cl">    <span class="kt">int</span> <span class="nf">maximumPoints</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&gt;&amp;</span> <span class="n">edges</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">coins</span><span class="p">,</span> <span class="kt">int</span> <span class="n">k</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">        <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">coins</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
</span></span><span class="line"><span class="cl">        <span class="k">this</span><span class="o">-&gt;</span><span class="n">coins</span> <span class="o">=</span> <span class="n">coins</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        <span class="k">this</span><span class="o">-&gt;</span><span class="n">k</span> <span class="o">=</span> <span class="n">k</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="n">graph</span><span class="p">.</span><span class="n">assign</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="p">());</span>
</span></span><span class="line"><span class="cl">        <span class="n">memo</span><span class="p">.</span><span class="n">assign</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="p">(</span><span class="mi">15</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">));</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">for</span> <span class="p">(</span><span class="k">auto</span><span class="o">&amp;</span> <span class="nl">edge</span> <span class="p">:</span> <span class="n">edges</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="n">graph</span><span class="p">[</span><span class="n">edge</span><span class="p">[</span><span class="mi">0</span><span class="p">]].</span><span class="n">push_back</span><span class="p">(</span><span class="n">edge</span><span class="p">[</span><span class="mi">1</span><span class="p">]);</span>
</span></span><span class="line"><span class="cl">            <span class="n">graph</span><span class="p">[</span><span class="n">edge</span><span class="p">[</span><span class="mi">1</span><span class="p">]].</span><span class="n">push_back</span><span class="p">(</span><span class="n">edge</span><span class="p">[</span><span class="mi">0</span><span class="p">]);</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">return</span> <span class="n">dfs</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">    <span class="p">}</span>
</span></span><span class="line"><span class="cl">    
</span></span><span class="line"><span class="cl">    <span class="kt">int</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">node</span><span class="p">,</span> <span class="kt">int</span> <span class="n">parent</span><span class="p">,</span> <span class="kt">int</span> <span class="n">t</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">        <span class="k">if</span> <span class="p">(</span><span class="n">t</span> <span class="o">&gt;=</span> <span class="mi">14</span><span class="p">)</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">if</span> <span class="p">(</span><span class="n">memo</span><span class="p">[</span><span class="n">node</span><span class="p">][</span><span class="n">t</span><span class="p">]</span> <span class="o">!=</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="k">return</span> <span class="n">memo</span><span class="p">[</span><span class="n">node</span><span class="p">][</span><span class="n">t</span><span class="p">];</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="c1">// 方式1：收集 coins[node] - k 分
</span></span></span><span class="line"><span class="cl">        <span class="kt">int</span> <span class="n">way1</span> <span class="o">=</span> <span class="p">(</span><span class="n">coins</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">&gt;&gt;</span> <span class="n">t</span><span class="p">)</span> <span class="o">-</span> <span class="n">k</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        <span class="c1">// 方式2：收集 floor(coins[node] / 2) 分
</span></span></span><span class="line"><span class="cl">        <span class="kt">int</span> <span class="n">way2</span> <span class="o">=</span> <span class="n">coins</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">&gt;&gt;</span> <span class="p">(</span><span class="n">t</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="nl">child</span> <span class="p">:</span> <span class="n">graph</span><span class="p">[</span><span class="n">node</span><span class="p">])</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="k">if</span> <span class="p">(</span><span class="n">child</span> <span class="o">!=</span> <span class="n">parent</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">                <span class="n">way1</span> <span class="o">+=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">child</span><span class="p">,</span> <span class="n">node</span><span class="p">,</span> <span class="n">t</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">                <span class="n">way2</span> <span class="o">+=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">child</span><span class="p">,</span> <span class="n">node</span><span class="p">,</span> <span class="n">t</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">            <span class="p">}</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">return</span> <span class="n">memo</span><span class="p">[</span><span class="n">node</span><span class="p">][</span><span class="n">t</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">way1</span><span class="p">,</span> <span class="n">way2</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">    <span class="p">}</span>
</span></span><span class="line"><span class="cl"><span class="p">};</span>
</span></span></code></pre></div>
</div>

<div class="codetab-panel" data-tab-name="Python">
  <div class="highlight"><pre tabindex="0" class="chroma"><code class="language-python" data-lang="python"><span class="line"><span class="cl"><span class="k">class</span> <span class="nc">Solution</span><span class="p">:</span>
</span></span><span class="line"><span class="cl">    <span class="k">def</span> <span class="nf">maximumPoints</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">edges</span><span class="p">:</span> <span class="n">List</span><span class="p">[</span><span class="n">List</span><span class="p">[</span><span class="nb">int</span><span class="p">]],</span> <span class="n">coins</span><span class="p">:</span> <span class="n">List</span><span class="p">[</span><span class="nb">int</span><span class="p">],</span> <span class="n">k</span><span class="p">:</span> <span class="nb">int</span><span class="p">)</span> <span class="o">-&gt;</span> <span class="nb">int</span><span class="p">:</span>
</span></span><span class="line"><span class="cl">        <span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">coins</span><span class="p">)</span>
</span></span><span class="line"><span class="cl">        <span class="n">graph</span> <span class="o">=</span> <span class="p">[[]</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">n</span><span class="p">)]</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">for</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span> <span class="ow">in</span> <span class="n">edges</span><span class="p">:</span>
</span></span><span class="line"><span class="cl">            <span class="n">graph</span><span class="p">[</span><span class="n">a</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">b</span><span class="p">)</span>
</span></span><span class="line"><span class="cl">            <span class="n">graph</span><span class="p">[</span><span class="n">b</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="n">memo</span> <span class="o">=</span> <span class="p">{}</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">def</span> <span class="nf">dfs</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">parent</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
</span></span><span class="line"><span class="cl">            <span class="k">if</span> <span class="n">t</span> <span class="o">&gt;=</span> <span class="mi">14</span><span class="p">:</span>
</span></span><span class="line"><span class="cl">                <span class="k">return</span> <span class="mi">0</span>
</span></span><span class="line"><span class="cl">            
</span></span><span class="line"><span class="cl">            <span class="k">if</span> <span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">t</span><span class="p">)</span> <span class="ow">in</span> <span class="n">memo</span><span class="p">:</span>
</span></span><span class="line"><span class="cl">                <span class="k">return</span> <span class="n">memo</span><span class="p">[(</span><span class="n">node</span><span class="p">,</span> <span class="n">t</span><span class="p">)]</span>
</span></span><span class="line"><span class="cl">            
</span></span><span class="line"><span class="cl">            <span class="c1"># 方式1：收集 coins[node] - k 分</span>
</span></span><span class="line"><span class="cl">            <span class="n">way1</span> <span class="o">=</span> <span class="p">(</span><span class="n">coins</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">&gt;&gt;</span> <span class="n">t</span><span class="p">)</span> <span class="o">-</span> <span class="n">k</span>
</span></span><span class="line"><span class="cl">            <span class="c1"># 方式2：收集 floor(coins[node] / 2) 分  </span>
</span></span><span class="line"><span class="cl">            <span class="n">way2</span> <span class="o">=</span> <span class="n">coins</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">&gt;&gt;</span> <span class="p">(</span><span class="n">t</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
</span></span><span class="line"><span class="cl">            
</span></span><span class="line"><span class="cl">            <span class="k">for</span> <span class="n">child</span> <span class="ow">in</span> <span class="n">graph</span><span class="p">[</span><span class="n">node</span><span class="p">]:</span>
</span></span><span class="line"><span class="cl">                <span class="k">if</span> <span class="n">child</span> <span class="o">!=</span> <span class="n">parent</span><span class="p">:</span>
</span></span><span class="line"><span class="cl">                    <span class="n">way1</span> <span class="o">+=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">child</span><span class="p">,</span> <span class="n">node</span><span class="p">,</span> <span class="n">t</span><span class="p">)</span>
</span></span><span class="line"><span class="cl">                    <span class="n">way2</span> <span class="o">+=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">child</span><span class="p">,</span> <span class="n">node</span><span class="p">,</span> <span class="n">t</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
</span></span><span class="line"><span class="cl">            
</span></span><span class="line"><span class="cl">            <span class="n">result</span> <span class="o">=</span> <span class="nb">max</span><span class="p">(</span><span class="n">way1</span><span class="p">,</span> <span class="n">way2</span><span class="p">)</span>
</span></span><span class="line"><span class="cl">            <span class="n">memo</span><span class="p">[(</span><span class="n">node</span><span class="p">,</span> <span class="n">t</span><span class="p">)]</span> <span class="o">=</span> <span class="n">result</span>
</span></span><span class="line"><span class="cl">            <span class="k">return</span> <span class="n">result</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">return</span> <span class="n">dfs</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
</span></span></code></pre></div>
</div>

<div class="codetab-panel" data-tab-name="C#">
  <div class="highlight"><pre tabindex="0" class="chroma"><code class="language-csharp" data-lang="csharp"><span class="line"><span class="cl"><span class="kd">public</span> <span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">    <span class="kd">private</span> <span class="n">List</span><span class="p">&lt;</span><span class="n">List</span><span class="p">&lt;</span><span class="kt">int</span><span class="p">&gt;&gt;</span> <span class="n">graph</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    <span class="kd">private</span> <span class="n">Dictionary</span><span class="p">&lt;(</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="p">),</span> <span class="kt">int</span><span class="p">&gt;</span> <span class="n">memo</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    <span class="kd">private</span> <span class="kt">int</span><span class="p">[]</span> <span class="n">coins</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    <span class="kd">private</span> <span class="kt">int</span> <span class="n">k</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    
</span></span><span class="line"><span class="cl">    <span class="kd">public</span> <span class="kt">int</span> <span class="n">MaximumPoints</span><span class="p">(</span><span class="kt">int</span><span class="p">[][]</span> <span class="n">edges</span><span class="p">,</span> <span class="kt">int</span><span class="p">[]</span> <span class="n">coins</span><span class="p">,</span> <span class="kt">int</span> <span class="n">k</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">        <span class="kt">int</span> <span class="n">n</span> <span class="p">=</span> <span class="n">coins</span><span class="p">.</span><span class="n">Length</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        <span class="k">this</span><span class="p">.</span><span class="n">coins</span> <span class="p">=</span> <span class="n">coins</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        <span class="k">this</span><span class="p">.</span><span class="n">k</span> <span class="p">=</span> <span class="n">k</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="n">graph</span> <span class="p">=</span> <span class="k">new</span> <span class="n">List</span><span class="p">&lt;</span><span class="n">List</span><span class="p">&lt;</span><span class="kt">int</span><span class="p">&gt;&gt;();</span>
</span></span><span class="line"><span class="cl">        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="p">=</span> <span class="m">0</span><span class="p">;</span> <span class="n">i</span> <span class="p">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="p">++)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="n">graph</span><span class="p">.</span><span class="n">Add</span><span class="p">(</span><span class="k">new</span> <span class="n">List</span><span class="p">&lt;</span><span class="kt">int</span><span class="p">&gt;());</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="n">memo</span> <span class="p">=</span> <span class="k">new</span> <span class="n">Dictionary</span><span class="p">&lt;(</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="p">),</span> <span class="kt">int</span><span class="p">&gt;();</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">foreach</span> <span class="p">(</span><span class="kt">var</span> <span class="n">edge</span> <span class="k">in</span> <span class="n">edges</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="n">graph</span><span class="p">[</span><span class="n">edge</span><span class="p">[</span><span class="m">0</span><span class="p">]].</span><span class="n">Add</span><span class="p">(</span><span class="n">edge</span><span class="p">[</span><span class="m">1</span><span class="p">]);</span>
</span></span><span class="line"><span class="cl">            <span class="n">graph</span><span class="p">[</span><span class="n">edge</span><span class="p">[</span><span class="m">1</span><span class="p">]].</span><span class="n">Add</span><span class="p">(</span><span class="n">edge</span><span class="p">[</span><span class="m">0</span><span class="p">]);</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">return</span> <span class="n">Dfs</span><span class="p">(</span><span class="m">0</span><span class="p">,</span> <span class="p">-</span><span class="m">1</span><span class="p">,</span> <span class="m">0</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">    <span class="p">}</span>
</span></span><span class="line"><span class="cl">    
</span></span><span class="line"><span class="cl">    <span class="kd">private</span> <span class="kt">int</span> <span class="n">Dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">node</span><span class="p">,</span> <span class="kt">int</span> <span class="n">parent</span><span class="p">,</span> <span class="kt">int</span> <span class="n">t</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">        <span class="k">if</span> <span class="p">(</span><span class="n">t</span> <span class="p">&gt;=</span> <span class="m">14</span><span class="p">)</span> <span class="k">return</span> <span class="m">0</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">if</span> <span class="p">(</span><span class="n">memo</span><span class="p">.</span><span class="n">ContainsKey</span><span class="p">((</span><span class="n">node</span><span class="p">,</span> <span class="n">t</span><span class="p">)))</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="k">return</span> <span class="n">memo</span><span class="p">[(</span><span class="n">node</span><span class="p">,</span> <span class="n">t</span><span class="p">)];</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="c1">// 方式1：收集 coins[node] - k 分</span>
</span></span><span class="line"><span class="cl">        <span class="kt">int</span> <span class="n">way1</span> <span class="p">=</span> <span class="p">(</span><span class="n">coins</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="p">&gt;&gt;</span> <span class="n">t</span><span class="p">)</span> <span class="p">-</span> <span class="n">k</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        <span class="c1">// 方式2：收集 floor(coins[node] / 2) 分</span>
</span></span><span class="line"><span class="cl">        <span class="kt">int</span> <span class="n">way2</span> <span class="p">=</span> <span class="n">coins</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="p">&gt;&gt;</span> <span class="p">(</span><span class="n">t</span> <span class="p">+</span> <span class="m">1</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">foreach</span> <span class="p">(</span><span class="kt">int</span> <span class="n">child</span> <span class="k">in</span> <span class="n">graph</span><span class="p">[</span><span class="n">node</span><span class="p">])</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="k">if</span> <span class="p">(</span><span class="n">child</span> <span class="p">!=</span> <span class="n">parent</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">                <span class="n">way1</span> <span class="p">+=</span> <span class="n">Dfs</span><span class="p">(</span><span class="n">child</span><span class="p">,</span> <span class="n">node</span><span class="p">,</span> <span class="n">t</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">                <span class="n">way2</span> <span class="p">+=</span> <span class="n">Dfs</span><span class="p">(</span><span class="n">child</span><span class="p">,</span> <span class="n">node</span><span class="p">,</span> <span class="n">t</span> <span class="p">+</span> <span class="m">1</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">            <span class="p">}</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="kt">int</span> <span class="n">result</span> <span class="p">=</span> <span class="n">Math</span><span class="p">.</span><span class="n">Max</span><span class="p">(</span><span class="n">way1</span><span class="p">,</span> <span class="n">way2</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">        <span class="n">memo</span><span class="p">[(</span><span class="n">node</span><span class="p">,</span> <span class="n">t</span><span class="p">)]</span> <span class="p">=</span> <span class="n">result</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        <span class="k">return</span> <span class="n">result</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    <span class="p">}</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span>
</span></span></code></pre></div>
</div>

<div class="codetab-panel" data-tab-name="JavaScript">
  <div class="highlight"><pre tabindex="0" class="chroma"><code class="language-javascript" data-lang="javascript"><span class="line"><span class="cl"><span class="kd">var</span> <span class="nx">maximumPoints</span> <span class="o">=</span> <span class="kd">function</span><span class="p">(</span><span class="nx">edges</span><span class="p">,</span> <span class="nx">coins</span><span class="p">,</span> <span class="nx">k</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">    <span class="kr">const</span> <span class="nx">n</span> <span class="o">=</span> <span class="nx">coins</span><span class="p">.</span><span class="nx">length</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    <span class="kr">const</span> <span class="nx">graph</span> <span class="o">=</span> <span class="nb">Array</span><span class="p">.</span><span class="nx">from</span><span class="p">({</span><span class="nx">length</span><span class="o">:</span> <span class="nx">n</span><span class="p">},</span> <span class="p">()</span> <span class="p">=&gt;</span> <span class="p">[]);</span>
</span></span><span class="line"><span class="cl">    <span class="kr">const</span> <span class="nx">memo</span> <span class="o">=</span> <span class="k">new</span> <span class="nx">Map</span><span class="p">();</span>
</span></span><span class="line"><span class="cl">    
</span></span><span class="line"><span class="cl">    <span class="k">for</span> <span class="p">(</span><span class="kr">const</span> <span class="p">[</span><span class="nx">a</span><span class="p">,</span> <span class="nx">b</span><span class="p">]</span> <span class="k">of</span> <span class="nx">edges</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">        <span class="nx">graph</span><span class="p">[</span><span class="nx">a</span><span class="p">].</span><span class="nx">push</span><span class="p">(</span><span class="nx">b</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">        <span class="nx">graph</span><span class="p">[</span><span class="nx">b</span><span class="p">].</span><span class="nx">push</span><span class="p">(</span><span class="nx">a</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">    <span class="p">}</span>
</span></span><span class="line"><span class="cl">    
</span></span><span class="line"><span class="cl">    <span class="kd">function</span> <span class="nx">dfs</span><span class="p">(</span><span class="nx">node</span><span class="p">,</span> <span class="nx">parent</span><span class="p">,</span> <span class="nx">t</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">        <span class="k">if</span> <span class="p">(</span><span class="nx">t</span> <span class="o">&gt;=</span> <span class="mi">14</span><span class="p">)</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="kr">const</span> <span class="nx">key</span> <span class="o">=</span> <span class="sb">`</span><span class="si">${</span><span class="nx">node</span><span class="si">}</span><span class="sb">,</span><span class="si">${</span><span class="nx">t</span><span class="si">}</span><span class="sb">`</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        <span class="k">if</span> <span class="p">(</span><span class="nx">memo</span><span class="p">.</span><span class="nx">has</span><span class="p">(</span><span class="nx">key</span><span class="p">))</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="k">return</span> <span class="nx">memo</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="nx">key</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="c1">// 方式1：收集 coins[node] - k 分
</span></span></span><span class="line"><span class="cl">        <span class="kd">let</span> <span class="nx">way1</span> <span class="o">=</span> <span class="p">(</span><span class="nx">coins</span><span class="p">[</span><span class="nx">node</span><span class="p">]</span> <span class="o">&gt;&gt;</span> <span class="nx">t</span><span class="p">)</span> <span class="o">-</span> <span class="nx">k</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        <span class="c1">// 方式2：收集 floor(coins[node] / 2) 分
</span></span></span><span class="line"><span class="cl">        <span class="kd">let</span> <span class="nx">way2</span> <span class="o">=</span> <span class="nx">coins</span><span class="p">[</span><span class="nx">node</span><span class="p">]</span> <span class="o">&gt;&gt;</span> <span class="p">(</span><span class="nx">t</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="k">for</span> <span class="p">(</span><span class="kr">const</span> <span class="nx">child</span> <span class="k">of</span> <span class="nx">graph</span><span class="p">[</span><span class="nx">node</span><span class="p">])</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="k">if</span> <span class="p">(</span><span class="nx">child</span> <span class="o">!==</span> <span class="nx">parent</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">                <span class="nx">way1</span> <span class="o">+=</span> <span class="nx">dfs</span><span class="p">(</span><span class="nx">child</span><span class="p">,</span> <span class="nx">node</span><span class="p">,</span> <span class="nx">t</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">                <span class="nx">way2</span> <span class="o">+=</span> <span class="nx">dfs</span><span class="p">(</span><span class="nx">child</span><span class="p">,</span> <span class="nx">node</span><span class="p">,</span> <span class="nx">t</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">            <span class="p">}</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span>
</span></span><span class="line"><span class="cl">        
</span></span><span class="line"><span class="cl">        <span class="kr">const</span> <span class="nx">result</span> <span class="o">=</span> <span class="nb">Math</span><span class="p">.</span><span class="nx">max</span><span class="p">(</span><span class="nx">way1</span><span class="p">,</span> <span class="nx">way2</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">        <span class="nx">memo</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">result</span><span class="p">);</span>
</span></span><span class="line"><span class="cl">        <span class="k">return</span> <span class="nx">result</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    <span class="p">}</span>
</span></span><span class="line"><span class="cl">    
</span></span><span class="line"><span class="cl">    <span class="k">return</span> <span class="nx">dfs</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span>
</span></span><span class="line"><span class="cl"><span class="p">};</span>
</span></span></code></pre></div>
</div>


  </div>
</div>




<div class="leetcode-links">
  <span class="leetcode-links-label">在 LeetCode 上运行：</span>
  <a href="https://leetcode.cn/problems/maximum-points-after-collecting-coins-from-all-nodes/" target="_blank" rel="noopener" class="lc-btn lc-cn">
    <svg viewBox="0 0 24 24" width="14" height="14" fill="currentColor"><path d="M13.483 0a1.374 1.374 0 0 0-.961.438L7.116 6.226l-3.854 4.126a5.266 5.266 0 0 0-1.209 2.104 5.35 5.35 0 0 0-.125.513 5.527 5.527 0 0 0 .062 2.362 5.83 5.83 0 0 0 .349 1.017 5.938 5.938 0 0 0 1.271 1.818l4.277 4.193.039.038c2.248 2.165 5.852 2.133 8.063-.074l2.396-2.392c.54-.54.54-1.414.003-1.955a1.378 1.378 0 0 0-1.951-.003l-2.396 2.392a3.021 3.021 0 0 1-4.205.038l-.02-.019-4.276-4.193c-.652-.64-.972-1.469-.948-2.263a2.68 2.68 0 0 1 .066-.523 2.545 2.545 0 0 1 .619-1.164L9.13 8.114c1.058-1.134 3.204-1.27 4.43-.278l3.501 2.831c.593.48 1.461.387 1.94-.207a1.384 1.384 0 0 0-.207-1.943l-3.5-2.831c-.8-.647-1.766-1.045-2.774-1.202l2.015-2.158A1.384 1.384 0 0 0 13.483 0zm-2.866 12.815a1.38 1.38 0 0 0-1.38 1.382 1.38 1.38 0 0 0 1.38 1.382H20.79a1.38 1.38 0 0 0 1.38-1.382 1.38 1.38 0 0 0-1.38-1.382z"/></svg>
    力扣中文版
  </a>
  <a href="https://leetcode.com/problems/maximum-points-after-collecting-coins-from-all-nodes/" target="_blank" rel="noopener" class="lc-btn lc-com">
    <svg viewBox="0 0 24 24" width="14" height="14" fill="currentColor"><path d="M13.483 0a1.374 1.374 0 0 0-.961.438L7.116 6.226l-3.854 4.126a5.266 5.266 0 0 0-1.209 2.104 5.35 5.35 0 0 0-.125.513 5.527 5.527 0 0 0 .062 2.362 5.83 5.83 0 0 0 .349 1.017 5.938 5.938 0 0 0 1.271 1.818l4.277 4.193.039.038c2.248 2.165 5.852 2.133 8.063-.074l2.396-2.392c.54-.54.54-1.414.003-1.955a1.378 1.378 0 0 0-1.951-.003l-2.396 2.392a3.021 3.021 0 0 1-4.205.038l-.02-.019-4.276-4.193c-.652-.64-.972-1.469-.948-2.263a2.68 2.68 0 0 1 .066-.523 2.545 2.545 0 0 1 .619-1.164L9.13 8.114c1.058-1.134 3.204-1.27 4.43-.278l3.501 2.831c.593.48 1.461.387 1.94-.207a1.384 1.384 0 0 0-.207-1.943l-3.5-2.831c-.8-.647-1.766-1.045-2.774-1.202l2.015-2.158A1.384 1.384 0 0 0 13.483 0zm-2.866 12.815a1.38 1.38 0 0 0-1.38 1.382 1.38 1.38 0 0 0 1.38 1.382H20.79a1.38 1.38 0 0 0 1.38-1.382 1.38 1.38 0 0 0-1.38-1.382z"/></svg>
    LeetCode 国际版
  </a>
</div>



## 复杂度分析

| 复杂度类型 | 分析 |
|-----------|------|
| 时间复杂度 | O(n × log(max(coins))) |
| 空间复杂度 | O(n × log(max(coins))) |

**说明：**
- 时间复杂度：每个节点最多被访问 14 次（因为 log₂(10⁴) ≈ 14），所以总时间复杂度为 O(n × 14) = O(n)
- 空间复杂度：记忆化数组的大小为 O(n × 14)，递归栈深度最大为 O(n)