收集树中金币【LC2603】
给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。
一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：
收集距离当前节点距离为 2 以内的所有金币，或者
移动到树中一个相邻节点。
你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。
如果你多次经过一条边，每一次经过都会给答案加一。
思路：拓扑排序+贪心
首先，我们可以去掉不包含金币的子树【步骤a】，因为访问其中任何一个点都毫无意义。
实现：拓扑排序，去除不含金币的叶子节点
如果所有在叶子上的金币全部都能收集到，那么我们可以收集到树上所有金币。而由于可以「收集距离当前节点距离为 2以内的所有金币」，因此可以再次去除两轮有金币的叶子【步骤b】，剩余的结点即为必须经过的结点
贪心：从距离有金币叶子为2的节点处出发【局部最优】，收集树中所有的金币，并且回到出发节点时经过的边数最少【全局最优】。
实现：再次进行拓扑排序
最终答案：从某个节点出发后，仍需要回到起点；因此最终答案为剩余边数乘以2。
实现1：统计每个必须经过的节点的入队时间，如果一条边的两个节点的入队时间均大于2，那么这条边必须经过两次
实现2：在拓扑排序时记录不需要遍历的边的数目【步骤a和步骤b的边数】，最后需要进行特判，如果所有节点均需要删除时，答案为-1，此时应与0取较大值
实现
无向图，节点度为1时为叶子
class Solution { public int collectTheCoins(int[] coins, int[][] edges) { int n = coins.length; List<Integer> g[] = new ArrayList[n]; Arrays.setAll(g, e -> new ArrayList<>()); var deg = new int[n]; for (var e : edges) { int x = e[0], y = e[1]; g[x].add(y); g[y].add(x); // 建图 ++deg[x]; ++deg[y]; } // 用拓扑排序「剪枝」：去掉没有金币的子树 var q = new ArrayDeque<Integer>(); for (int i = 0; i < n; ++i) if (deg[i] == 1 && coins[i] == 0) // 无金币叶子 q.add(i); while (!q.isEmpty()) { int x = q.peek(); q.pop(); for (int y : g[x]) if (--deg[y] == 1 && coins[y] == 0)// 无金币叶子 q.add(y); } // 再次拓扑排序 for (int i = 0; i < n; ++i) if (deg[i] == 1 && coins[i] == 1) // 有金币叶子 q.add(i); if (q.size() <= 1) return 0; // 至多一个有金币的叶子，直接收集 var time = new int[n]; while (!q.isEmpty()) { int x = q.peek(); q.pop(); for (int y : g[x]) if (--deg[y] == 1) { time[y] = time[x] + 1; // 记录入队时间 q.add(y); } } // 统计答案 int ans = 0; for (var e : edges) if (time[e[0]] >= 2 && time[e[1]] >= 2) ans += 2; return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/collect-coins-in-a-tree/solutions/2191371/tuo-bu-pai-xu-ji-lu-ru-dui-shi-jian-pyth-6uli/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
时间复杂度：O ( E + V ) ，E表示邻边的跳数，V为结点的个数
空间复杂度：O ( V )
实现2
class Solution { public int collectTheCoins(int[] coins, int[][] edges) { int n = coins.length; List<Integer> g[] = new ArrayList[n]; Arrays.setAll(g, e -> new ArrayList<>()); var deg = new int[n]; for (var e : edges) { int x = e[0], y = e[1]; g[x].add(y); g[y].add(x); // 建图 deg[x]++; deg[y]++; // 统计每个节点的度数（邻居个数） } int leftEdges = n - 1; // 剩余边数 // 拓扑排序，去掉没有金币的子树 var q = new ArrayDeque<Integer>(); for (int i = 0; i < n; i++) { if (deg[i] == 1 && coins[i] == 0) { // 没有金币的叶子 q.add(i); } } while (!q.isEmpty()) { leftEdges--; // 删除节点到其父节点的边 for (int y : g[q.poll()]) { if (--deg[y] == 1 && coins[y] == 0) { // 没有金币的叶子 q.add(y); } } } // 再次拓扑排序 for (int i = 0; i < n; i++) { if (deg[i] == 1 && coins[i] == 1) { // 有金币的叶子（判断 coins[i] 是避免把没有金币的叶子也算进来） q.add(i); } } leftEdges -= q.size(); // 删除所有叶子（到其父节点的边） for (int x : q) { // 遍历所有叶子 for (int y : g[x]) { if (--deg[y] == 1) { // y 现在是叶子了 leftEdges--; // 删除 y（到其父节点的边） } } } return Math.max(leftEdges * 2, 0); } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/collect-coins-in-a-tree/solutions/2191371/tuo-bu-pai-xu-ji-lu-ru-dui-shi-jian-pyth-6uli/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
时间复杂度：O ( E + V ) ，E表示邻边的跳数，V为结点的个数
空间复杂度：O ( V )
- 升级：如果把题目中的 2 换成 0,1,2,3,⋯ ,n−1，你能把这些情况对应的答案全部算出来吗？
遍历所有的边，如果两个节点的入队时间均大于q（最大距离），那么表示这条边必须要经过，结果+2
