2023-09-03：用go编写。给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 给你整数 n 和一个长度为

2023-09-03：用go语言编写。给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1

给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，

其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。

再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，

1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

收集距离当前节点距离为 2 以内的所有金币，或者 移动到树中一个相邻节点。

你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]。

输出：2。

来自左程云。

答案2023-09-03：

代码思路：

1.创建图结构和入度数组，并初始化空图和入度数组。

2.遍历边数组，将边的两个节点加入图中，同时更新入度数组。

3.创建队列，并将所有入度为1且节点上金币为0的节点加入队列。

4.使用BFS算法遍历队列，将入度-1并将入度为1且节点上金币为0的相邻节点加入队列。

5.继续遍历队列，将入度-1并记录节点的排名，并将入度为1的相邻节点加入队列。

6.计算满足条件的边数，即排名大于等于2的边。

7.返回计数值作为最少经过的边数。

总的时间复杂度：O(n)，其中n为节点数量，需要遍历边数组和节点数组，同时进行BFS操作。

总的额外空间复杂度：O(n)，需要创建图结构、入度数组和队列。

go完整代码如下：

在这里插入图片描述rust完整代码如下：

在这里插入图片描述c++完整代码如下：

在这里插入图片描述c完整代码如下：

在这里插入图片描述