Video Explanation (How to optimise brute force solution)
Explanation\n\nClick here for the video\n\n# Code\n\ntypedef long long int ll;\nconst ll NO_VALUE = 1e9;\n\nclass Solution {\n    int n;\n    vector<vector<int>
# Explanation\n\n[Click here for the video](https://youtu.be/1awKkZQuWhU)\n\n# Code\n```\ntypedef long long int ll;\nconst ll NO_VALUE = 1e9;\n\nclass Solution {\n    int n;\n    vector<vector<int>> g;\n    vector<int> cost;\n    \n    vector<vector<ll>> val;\n    vector<ll> coins;\n    \n    void CalculateCoins (int src, int par) {\n        vector<ll> child_val = {cost[src]};\n        \n        for (auto i : g[src]) {\n            if (i == par) continue;\n            \n            CalculateCoins (i, src);\n            for (auto i : val[i]) child_val.push_back(i);\n        }\n        sort (child_val.begin(), child_val.end());\n        \n        if (child_val.size() < 3) {\n            coins[src] = 1;\n            val[src] = child_val;\n        }\n        else {\n            int n = child_val.size();        \n            ll max_product = -1e18;\n            max_product = max (max_product, child_val[0]*child_val[1]*child_val[n-1]);\n            max_product = max (max_product, child_val[n-1]*child_val[n-2]*child_val[n-3]);\n    \n            coins[src] = max_product < 0? 0 : max_product;\n            \n            if (child_val.size() < 6) val[src] = child_val;\n            else val[src] = {child_val[0], child_val[1], child_val[n-3], child_val[n-2], child_val[n-1]};\n        }\n    }\n    \npublic:\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& _cost) {\n        n = _cost.size();\n        \n        g.clear(), val.clear(), cost.clear(), coins.clear(); \n        val.resize(n), g.resize(n), cost.resize(n), coins.resize(n);\n        cost = _cost;\n        \n        for (auto e: edges) {\n            g[e[0]].push_back(e[1]);\n            g[e[1]].push_back(e[0]);\n        }\n        \n        CalculateCoins(0, -1);\n        return coins;\n    }\n};\n```
['C++']