Readme

2603.Collect-Coins-in-a-Tree

首先，对于那些处于端点位置的非coin节点、及全部由非coin节点组成支链，我们注定是不会去理会的。所以我们可以第一步进行“剪枝”，用拓扑排序的方法，从度为1的非coin节点开始，一层一层往内圈剥洋葱，将这些多余的分支砍去。剩下的图形，叶子节点必然都是coin；当然也可能存在一些非coin的节点，但它们都位于去往其他coin节点的必经之路上，我们也必须去理会。

接下来考虑考虑题目中说，Collect all the coins that are at a distance of at most 2 from the current vertex. 这就意味着我们不必走到每个端点去收集coin，只要走到端点之前两步的位置就可以收集。所以我们可以进一步将这些不用到达的节点都砍去。这里我们同样可以用拓扑排序的方法，从度为1的节点开始，一层一层往内剥洋葱，从小到大来标记每个节点的深度。这里的深度的定义就是，从该点到它的所有的子孙节点里的最大距离。举个例子，假设A->B，A->C->D->E，其中B和E都是端点，那么A的深度就是4.

通过拓扑排序标记了所有节点从外圈到内圈的深度之后，我们发现，深度大于等于3的节点是我们必须访问的。而深度小于3的节点我们不需要访问，只需要走到深度等于3的节点就能收集到端点处的coin（如果有的话）。假设深度大于等于3的节点的个数有m个，因为这m个点必然是联通的，所以对应有m-1条边。我们注意到，起点和终点必须在同一处，这就意味着无论如何每条边我们必须走两次（一来一回），所以最终的答案就是2(m-1)，起点选在这m个节点的任意一个都可。

特别注意，如果m等于0，直接返回0.