2603. 收集树中金币

2603.收集树中金币

题目描述：

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

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

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

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

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

数据范围：

$1\le n \le 3 \times 10^4$

题解：

无根树需要层次遍历。由于不存在根节点，因此层次遍历只能从叶子节点出发，参考拓扑排序，每次把所有度为 $1$ 的节点全放进去，然后取出节点，更新度，继续。

该题可以先把所有的非金币叶子节点全删了。因为根本不会到达这些节点，删去不影响，虚拟删除，只修改度。

剩余所有的叶子节点就是金币节点，然后继续删除两层节点。剩余的就是必须经过的节点了，而且是一棵树的样式，遍历时所有的边，每条边都刚好会被遍历两遍。因为树的形式，只能一次进来，一次出去，刚好两次。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int collectTheCoins(vector<int> &coins, vector<vector<int>> &edges)
    {
        int n = coins.size();
        queue<int> q;
        vector<int> deg(n);
        vector<vector<int>> g(n);
        for (auto &edge : edges)
        {
            int u = edge[0], v = edge[1];
            g[u].emplace_back(v);
            g[v].emplace_back(u);
            deg[u]++;
            deg[v]++;
        }
        for (int i = 0; i < n; ++i)
        {
            if (coins[i] == 0 && deg[i] == 1)
            {
                q.push(i);
            }
        }
        // 先删掉普通的非金币叶子节点
        while (q.size())
        {
            auto u = q.front();
            --deg[u];
            q.pop();
            for (int i = 0; i < g[u].size(); ++i)
            {
                int v = g[u][i];
                --deg[v];
                if (deg[v] == 1 && coins[v] == 0)
                {
                    q.push(v);
                }
            }
        }
        for (int t = 0; t < 2; ++t)
        {
            for (int i = 0; i < n; ++i)
            {
                if (deg[i] == 1)
                {
                    q.push(i);
                }
            }
            while (q.size())
            {
                auto u = q.front();
                --deg[u];
                q.pop();
                for (int i = 0; i < g[u].size(); ++i)
                {
                    int v = g[u][i];
                    --deg[v];
                }
            }
        }
        int ans = 0;
        for(auto& edge: edges)
        {
            int u = edge[0], v = edge[1];
            if(deg[u] > 0 && deg[v] > 0)
            {
                ans++;
                // cout << u << ", " << v << endl;
            }
        }
        return ans * 2;
    }
};