[C++] DFS and MultiSet
Intuition\n Describe your first thoughts on how to solve this problem. \n- Use DFS to travel the tree and collect information from all child nodes\n- For each n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Use DFS to travel the tree and collect information from all child nodes\n- For each node, we only consider the following information:\n  - `size`: the size of the subtree starting from the current node\n  - `pos`: the maximum 3 positive integers in the current subtree\n  - `neg`: the minimum 2 negative integers in the current subtree\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Build the graph\n- Use DFS to collect information for each node\n- Get coin for each node\n\n# Complexity\n- Time complexity: $$O(V + E) = O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(V + E) = O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = cost.size();\n        \n        // build the graph\n        vector<vector<int>> graph(n);\n        for (auto& edge : edges) {\n            graph[edge[0]].push_back(edge[1]);\n            graph[edge[1]].push_back(edge[0]);\n        }\n        \n        // use DFS to collect information for each node\n        vector<Node> nodes(n);\n        dfs(graph, nodes, cost, 0, -1);\n        \n        // get coin for each node\n        vector<long long> coin(n);\n        for (int i = 0; i < n; i++) coin[i] = getCoin(nodes[i]);\n        return coin;\n    }\nprivate:\n    struct Node {\n        int size;\n        multiset<int> pos;\n        multiset<int> neg;\n    };\n    void dfs(vector<vector<int>>& graph, vector<Node>& nodes, vector<int>& cost, int curr, int prev) {\n        // update the current node\n        nodes[curr].size = 1;\n        if (cost[curr] > 0) nodes[curr].pos.insert(cost[curr]);\n        if (cost[curr] < 0) nodes[curr].neg.insert(cost[curr]);\n        \n        // collect the information from the next nodes\n        for (auto& next : graph[curr]) {\n            // skip the parent node\n            if (next == prev) continue;\n\n            // go to the next child node\n            dfs(graph, nodes, cost, next, curr);\n            nodes[curr].size += nodes[next].size;\n            nodes[curr].pos.insert(nodes[next].pos.begin(), nodes[next].pos.end());\n            nodes[curr].neg.insert(nodes[next].neg.begin(), nodes[next].neg.end());\n        \n            // keep the maximum 3 positive integers \n            while (nodes[curr].pos.size() > 3) nodes[curr].pos.erase(nodes[curr].pos.begin());\n            // keep the minimum 2 negative integers\n            while (nodes[curr].neg.size() > 2) nodes[curr].neg.erase(--nodes[curr].neg.end());\n        }\n    }\n    long long getCoin(Node& node) {\n        // base case\n        if (node.size < 3) return 1;\n\n        // collect coins\n        vector<int> coins;\n        for (auto& c : node.pos) coins.push_back(c);\n        for (auto& c : node.neg) coins.push_back(c);\n\n        // find the maximum product\n        long long best = LONG_LONG_MIN;\n        for (int a = 0; a < coins.size(); a++) {\n            for (int b = a + 1; b < coins.size(); b++) {\n                for (int c = b + 1; c < coins.size(); c++) {\n                    long long product = 1LL * coins[a] * coins[b] * coins[c];\n                    best = max(best, product);\n                }\n            }\n        }\n        \n        // if the maximum product is negative, replace with `0`\n        if (best < 0) return 0;\n        return best;\n    }\n};\n```
['Depth-First Search', 'Graph', 'Ordered Set', 'C++']