Solution

Method 1 – Prune Leaves and BFS

Intuition

We can prune all leaves that do not have coins, as they are not needed for collection. After pruning, the minimum number of edges to traverse is twice the number of remaining edges minus the ability to start and end within distance 2 of all coins (so we can avoid traversing the outermost two layers).

Approach

Build the tree as an adjacency list.
Prune all leaves without coins by repeatedly removing them and updating their neighbors.
After pruning, perform two rounds of leaf removal (BFS) to simulate the ability to collect coins within distance 2.
The answer is the number of remaining edges times 2 (since each edge is traversed twice).

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {\n        int n = coins.size();\n        vector<vector<int>> g(n);\n        vector<int> deg(n);\n        for (auto& e : edges) {\n            g[e[0]].push_back(e[1]);\n            g[e[1]].push_back(e[0]);\n            deg[e[0]]++;\n            deg[e[1]]++;\n        }\n        queue<int> q;\n        for (int i = 0; i < n; ++i) if (deg[i] == 1 && coins[i] == 0) q.push(i);\n        int rem = n;\n        while (!q.empty()) {\n            int u = q.front(); q.pop(); rem--;\n            for (int v : g[u]) if (--deg[v] == 1 && coins[v] == 0) q.push(v);\n        }\n        for (int t = 0; t < 2; ++t) {\n            for (int i = 0; i < n; ++i) if (deg[i] == 1) q.push(i);\n            int sz = q.size();\n            while (sz--) {\n                int u = q.front(); q.pop(); rem--;\n                for (int v : g[u]) if (--deg[v] == 1) q.push(v);\n            }\n        }\n        return rem <= 1 ? 0 : (rem - 1) * 2;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> collectTheCoins</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> coins</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shi

Related Tags