Simple Data Structure Approach
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 []\nclass Node\n{\npublic:\n    int cnt;\n    vector<int> A, B;\n    Node(): cnt(0) {}\n    Node(int k)\n    {\n        cnt = 1;\n        if (k > 0) A.push_back(k);\n        else B.push_back(abs(k));\n    }\n    void update(Node *child)\n    {\n        cnt += child->cnt;\n        A.insert(A.end(), child->A.begin(), child->A.end());\n        B.insert(B.end(), child->B.begin(), child->B.end());\n        sort(A.begin(), A.end(), greater<int>());\n        sort(B.begin(), B.end(), greater<int>());\n        A.resize(min((int)A.size(), 3));\n        B.resize(min((int)B.size(), 2));\n    }\n    long long cacl()\n    {\n        if (cnt < 3) return 1;\n        long long res = 0;\n        if (A.size() == 3)\n            res = 1LL*A[0]*A[1]*A[2];\n        if (A.size() >= 1 && B.size() == 2)\n            res = max(res, 1LL*A[0]*B[0]*B[1]);\n        return res;\n    }\n};\nclass Solution {\npublic:\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) \n    {\n        int n = edges.size()+1;\n        vector<vector<int>> adj(n);\n        for (auto &e:edges)\n        {\n            adj[e[0]].push_back(e[1]);\n            adj[e[1]].push_back(e[0]);\n        }\n        Node *root = new Node(cost[0]);\n        vector<long long> res(n, 0);\n        dfs(-1, 0, res, cost, adj);\n        return res;\n    }\nprivate:\n    Node* dfs(int par, int cur, vector<long long> &res, vector<int> &cost, vector<vector<int>> &adj)\n    {\n        Node *tmp = new Node(cost[cur]);\n        for (auto &nxt:adj[cur])\n        {\n            if (nxt == par) continue;\n            Node *child = dfs(cur, nxt, res, cost, adj);\n            tmp->update(child);\n            delete(child);\n        }\n        long long ans = tmp->cacl();\n        res[cur] = ans;\n        return tmp;\n    }\n};\n```
['C++']