LC2603 收集树中金币

利用了拓扑排序思想的趣题。

答案要求统计“走过的边数”，这个不是很好统计，但是统计“哪些点不需要去”比较简单：

1. 没有金币的子树不需要去；
2. 删去 1 之后的叶子结点不需要去；
3. 删去 1,2 之后的叶子结点不需要去。

可以证明，其他的点都需要去到。

删去上述结点的依据是度数（都是叶子结点）和金币，自然地想到使用拓扑排序处理。

细节上，因为答案要求的是边而不是点，故需要将“删除点”转化为“删除点到自己父节点的边”，用一个变量统计剩余边数即可；如果所有的点全部删完，变量的值变成 \(-1\)，需要特判；因为要求回到出发点，答案为剩余边数乘以 \(2\)。

拓扑排序应当注意逐层删除，实现时切勿跨层删点，否则会导致点的度数出错。

下面是 AC 代码：

int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n = coins.size();
        int m = n - 1;
        vector<vector<int>> g(n);
        vector<int> deg(n);
        for(auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
            ++deg[e[0]], ++deg[e[1]];
        }
        queue<int> q;
        for(int i = 0; i < n; i++) {
            if(deg[i] == 1 && !coins[i]){ //没有金币的叶子结点
                q.push(i);
            }
        }
        while(!q.empty()) { //第一次拓扑排序，把没有金币的子树全部消灭
            --m;
            int u = q.front();
            q.pop();
            for(int v : g[u]){
                if(--deg[v] == 1 && !coins[v]){
                    q.push(v);
                }
            }
        }
        for(int u = 0; u < n; u++) {
            if(deg[u] == 1 && coins[u]) { // 有金币的叶子结点
                q.push(u);
            }
        }
        m -= q.size();
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int v : g[u]) {
                if(--deg[v] == 1) { // 仅删除两层，不再入队
                    m--;
                }
            }
        }
        return max(m * 2, 0); // 避免边数出现 -1
    }