提示 1
定义一个点的度数为其邻居个数。如果一个点的度数为 1，那么这个点叫做叶子节点，例如示例 2 的 3,4,6,7 都是叶子节点。

如果叶子节点没有金币，我们有必要移动到叶子节点吗？没有必要。

那么可以先把这些没有金币的叶子节点去掉。如果去掉后又产生了新的没有金币的叶子节点，就继续去掉。

怎么实现？拓扑排序。一开始，把没有金币的叶子节点都加到队列中。然后不断循环直到队列为空。每次循环，弹出队首的节点 x，并删除 x 及其邻居之间的边。我们并不需要实际删除边，只需要把邻居的度数减少 1。如果一个邻居的度数减少为 1 且没有金币，就加到队列中，继续拓扑排序。

提示 2
看示例 2，在去掉节点 6 之后，现在每个叶子节点上都有金币。

由于可以「收集距离当前节点距离为 2 以内的所有金币」，我们没有必要移动到叶子节点再收集，而是移动到叶子节点的父节点的父节点，就能收集到叶子节点上的金币。

那么，去掉所有叶子，然后再去掉新产生的叶子，剩余节点就是必须要访问的节点。

提示 3
由于题目要求最后回到出发点，无论从哪个点出发，每条边都必须走两次。这是因为把出发点作为树根，递归遍历这棵树，那么往下「递」是一次，往上「归」又是一次，每条边都会经过两次。

所以答案就是剩余边数乘 2。当我们删除节点时，也可以看成是删除这个点到其父节点的边。

特别地，如果所有点都要被删除，那么当剩下两个点时，这两个点之间的边我们会删除两次，这会导致剩余边数等于 −1，而此时答案应该是 0。所以最后答案要和 0 取最大值。

vector<int> e[30005];
void add(int a, int b) {e[a].push_back(b);e[b].push_back(a);
}
class Solution {
public:int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {int n = coins.size();vector<int> has(n + 1);// 记录是否被删除vector<int> record(n + 1);for (int i = 0; i < n; i++) {e[i].clear();}for (int i = 0; i < edges.size(); i++) {int u = edges[i][0], v = edges[i][1];record[u]++; record[v]++;add(u, v);}queue<int> q;for (int i = 0; i < n; i++) {if (record[i] == 1 && coins[i] != 1) {q.push(i); //cout << i<< " ";}}while (q.size()) {int u = q.front(); q.pop(); //cout << u << " ";if (has[u])  continue;has[u] = 1;for (auto v : e[u]) {record[v]--;if (record[v] == 1 && coins[v] == 0) {q.push(v);}}}// 上面已经对没有用的节点进行了处理for (int i = 0; i < n; i++) {if (coins[i] && record[i] == 1) {q.push(i); //cout << i << " ";}}while (q.size()) {int u = q.front(); q.pop();if (has[u]) continue; //cout << u << " ";has[u] = 1;for (auto v : e[u]) {record[v]--;if (record[v] == 1) {if (v == 2) cout << u;has[v] = 1; //cout << v << " ";} // 没必要再放入队列中}}int ans = 0;for (int i = 0; i < n; i++) {if (!has[i]) {ans++; //cout << i << " ";}}return (ans - 1) * 2;}
};