Brute Force | Beginner's Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\n#define ll long long\nclass Solution {\npublic:\n    vector<vector<int>> adj;\n    vector<ll> ans;\n    vector<int> sub, cost;\n    vector<int> p1, p2, p3; \n    vector<int> s1, s2;     \n    int n;\n\n    int dfs(int node, int par) {\n        int curr = 1;\n        for (auto x : adj[node]) {\n            if (x == par)\n                continue;\n            curr += dfs(x, node);\n        }\n        sub[node] = curr;\n        return curr;\n    }\n\n    void dfs1(int node, int par) {\n        p1[node] = p2[node] = p3[node] = INT_MIN;\n        s1[node] = s2[node] = INT_MAX;\n\n        int current_cost = cost[node];\n        update_max(p1[node], p2[node], p3[node], current_cost);\n        update_min(s1[node], s2[node], current_cost);\n\n        for (auto x : adj[node]) {\n            if (x == par)\n                continue;\n            dfs1(x, node);\n\n            update_max(p1[node], p2[node], p3[node], p1[x]);\n            update_max(p1[node], p2[node], p3[node], p2[x]);\n            update_max(p1[node], p2[node], p3[node], p3[x]);\n\n            update_min(s1[node], s2[node], s1[x]);\n            update_min(s1[node], s2[node], s2[x]);\n        }\n    }\n\n    void update_max(int& first, int& second, int& third, int val) {\n        if (val > first) {\n            third = second;\n            second = first;\n            first = val;\n        } else if (val > second) {\n            third = second;\n            second = val;\n        } else if (val > third) {\n            third = val;\n        }\n    }\n\n    void update_min(int& first, int& second, int val) {\n        if (val < first) {\n            second = first;\n            first = val;\n        } else if (val < second) {\n            second = val;\n        }\n    }\n\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& c) {\n        cost = c;\n        n = edges.size() + 1;\n        adj.resize(n);\n        sub.resize(n, 0);\n        ans.resize(n, 0);\n        p1.resize(n, INT_MIN);\n        p2.resize(n, INT_MIN);\n        p3.resize(n, INT_MIN);\n        s1.resize(n, INT_MAX);\n        s2.resize(n, INT_MAX);\n\n        for (auto e : edges) {\n            adj[e[0]].push_back(e[1]);\n            adj[e[1]].push_back(e[0]);\n        }\n\n        dfs(0, -1);\n        dfs1(0, -1);\n\n        for (int i = 0; i < n; i++) {\n            if (sub[i] < 3) {\n                ans[i] = 1;\n            } else {\n                ll product = 1LL * p1[i] * p2[i] * p3[i];\n                product = max(product, 1LL * s1[i] * s2[i] * p1[i]);\n                ans[i] = (product < 0) ? 0 : product;\n            }\n        }\n\n        return ans;\n    }\n};\n\n```
['C++']