✅🔥Easy Solution🔥with explanation🔥
Approach\n\nWe will be counting the nodes and putting coins on them by DFS.\n\nSo, if there is less than 3 nodes in the sub tree then just put 1 coin on the nod
# Approach\n\nWe will be counting the nodes and putting coins on them by DFS.\n\nSo, if there is less than 3 nodes in the sub tree then just put 1 coin on the node but if there is more nodes then we will maximize the multiplication of costs of child nodes and the current node itself.\n\n<b>To maximize the product we have to tackle some cases :</b>\n>> Note: We will only keep track of 3 greatest positive numbers and 3 smallest negative (more the negative, greater the magnitude) numbers in the subtree.\n1. If we have only positive costs in the subtree then just pick 3 maximum costs and multiply them.\n2. If we have only negative costs then the answer will also be negative so we will put 0 coins.\n3. Now, the critical part : \n    a. If we have 1 negative and rest positive means at least 2 +ve (there should be 3 nodes to enter in these cases else the answer is directly 1) and 1 -ve then also the answer will be 0 because the multiplication will be -ve.\n    b. If we have at least 2 -ve and rest +ve then the maximum product will be `max(neg[0] * neg[1] * pos[0], pos[0] * pos[1] * pos[2])`\n\n**Note: For better understanding of these cases checkout the code of getMaxVal()**\n\n\n# Code\n```\ntypedef long long int LLI;\ntypedef vector<LLI> vli;\nconst int N = 2 * (1e4) + 5;\n\n#define printVect(v)      \\\n    for (int x : v)       \\\n    {                     \\\n        cout << x << " "; \\\n    }                     \\\n    cout << endl;\n\n\nclass CC {\n    public:\n    vli p; // array for +ve numbers\n    vli n; // array for -ve numbers\n    LLI nodeCount;\n    \n    CC() {\n        vli t;\n        p = t;\n        n = t;\n        nodeCount = 1;\n    }\n};\n\nclass Solution {\npublic:\n    \n    bool isVisited[N];\n    \n    LLI getMaxVal(vli &p, vli &n) {  // p -> Array of +ve numbers // n -> Array of -ve numbers\n        if (p.size() + n.size() < 3) return 1;\n        \n        sort(p.begin(), p.end(), greater<LLI>());\n        sort(n.begin(), n.end());\n        \n        LLI ans = 0;\n        \n        if (n.size() >= 2  &&  p.size() >= 1) {\n            ans = max(ans, n[0] * n[1] * p[0]);\n            if (p.size() >= 3) {\n                ans = max(ans, p[0] * p[1] * p[2]);\n            }\n        }\n        \n        if (n.size() < 2  &&  p.size() >= 3) {\n            ans = max(ans, p[0] * p[1] * p[2]);\n        }\n        \n        return ans;\n    }\n    \n\n    // This function will select the maximum costs from the sub trees of current node\n    CC updateMx(CC a, CC b) {\n        sort(a.p.begin(), a.p.end(), greater<LLI>());\n        sort(a.n.begin(), a.n.end());\n        \n        sort(b.p.begin(), b.p.end(), greater<LLI>());\n        sort(b.n.begin(), b.n.end());\n        \n        CC ans;\n        ans.nodeCount = a.nodeCount + b.nodeCount;\n        \n        int i = 0, j = 0;\n        while (i < a.p.size()  &&  j < b.p.size()  &&  ans.p.size() <= 3) {\n            if (a.p[i] > b.p[j]) {\n                ans.p.push_back(a.p[i]);\n                i++;\n            } else {\n                ans.p.push_back(b.p[j]);\n                j++;\n            }\n        }\n        \n        while (ans.p.size() <= 3  &&  i < a.p.size()) {\n            ans.p.push_back(a.p[i]);\n            i++;\n        }\n        \n        \n        while (ans.p.size() <= 3  &&  j < b.p.size()) {\n            ans.p.push_back(b.p[j]);\n            j++;\n        }\n        \n        \n        i = 0, j = 0;\n        while (i < a.n.size()  &&  j < b.n.size()  &&  ans.n.size() <= 3) {\n            if (a.n[i] < b.n[j]) {\n                ans.n.push_back(a.n[i]);\n                i++;\n            } else {\n                ans.n.push_back(b.n[j]);\n                j++;\n            }\n        }\n        \n        while (ans.n.size() <= 3  &&  i < a.n.size()) {\n            ans.n.push_back(a.n[i]);\n            i++;\n        }\n        \n        \n        while (ans.n.size() <= 3  &&  j < b.n.size()) {\n            ans.n.push_back(b.n[j]);\n            j++;\n        }\n        \n        return ans;\n    }\n    \n    CC helper(LLI node, unordered_map<LLI, vli> &mp, vector<int>& cost, vli &ans) {\n        isVisited[node] = true;\n        \n        int sN = 0;\n        CC c;\n        if (cost[node] < 0) {\n            c.n.push_back(cost[node]);  // insert in the negative values array\n        } else {\n            c.p.push_back(cost[node]);  // insert in the positive values array\n        }\n        \n        for (int child: mp[node]) {\n            if (isVisited[child]) continue;\n            sN++;\n            c = updateMx(c, helper(child, mp, cost, ans));\n        }\n        \n        \n        if (c.nodeCount < 3) {\n            ans[node] = 1;\n        } else {\n            ans[node] = getMaxVal(c.p, c.n);\n        }\n        return c;\n    }\n    \n    \n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        memset(isVisited, false, sizeof(isVisited));\n        unordered_map<LLI, vli> mp;\n        vli ans(cost.size());\n        \n        for (auto &v: edges) {\n            mp[v[0]].push_back(v[1]);\n            mp[v[1]].push_back(v[0]);\n        }\n        \n        helper(0, mp, cost, ans);\n        return ans;\n    }\n};\n```\n![5603a074-a878-4961-9d52-ab90764bd0eb_1703290787.4250824.png](https://assets.leetcode.com/users/images/3cd380af-cd7c-4bb7-9ee1-99411de054a3_1703351644.9171157.png)\n
['Depth-First Search', 'Graph', 'Recursion', 'Sorting', 'C++']