C++ O(n) tree traversal with incremental aggregation; no sorting, easy-to-understand  and modular
Intuition\nDP on tree. \nWe can gather the results from each child vertex, then aggregate them at the parent node. \nFor example, we can gather the max positive
# Intuition\nDP on tree. \nWe can gather the results from each child vertex, then aggregate them at the parent node. \nFor example, we can gather the max positive (and min negative) product of two cost-values (e.g. `a*b`) from the subtree, and gather the max positive (and min negative) cost-value from ST, then we can combine them to get the max product of three cost-values (e.g. `a*b*c`).\n\n# Approach\nFor each subtree, gather these items:\n* the max product of 3 distinct items. this is the `best` field \n* the max positive (and min negative) products of 2 distinct items. These are `posiTwoProd` and `negaTwoProd` fields. \n* the max positive value, and the min negative values. These are the `posiMax` and `negMax` fields.\n\nthen we can aggregate and combine the results at the parent node, to figure out the new `best` product, and maintain all the other fields of the `Results` struct.\n\n## Incremental updates without sorting\nWe can incrementally update or aggregate each child\'s result with the parent\'s, and don\'t have to hold all children\'s results in memory. \nSo there\'s no need to sort, and complexity is as low as O(n).\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```cpp []\n// Idea: DP, Tree DP, tree traversal.\n// for each subtree, gather these items:\n// the max product of 3 distinct items\n// the max (positive and negative) abs products of 2 distinct items.\n// the max positive value, and the min negative values with max abs, if any.\n// then we can aggregate and combine the results at the parent node.\n// Complexity: O(n)\nclass Solution {\n    vector<long long> _coins;\n    vector<vector<int>> _g;\n    vector<int> _cost;\n\n    struct Results {\n        long long best = 0, posiTwoProd = 0, negaTwoProd = 0, posiMax = 0,\n                  negMax = 0, vtxCount = 0;\n    };\n\n    Results traverse(int vtx, int parent) {\n        Results res;\n        res.vtxCount = 1;\n        if (_cost[vtx] > 0) {\n            res.posiMax = _cost[vtx];\n        } else {\n            res.negMax = _cost[vtx];\n        }\n        long long best = 0;\n        for (int nbr : _g[vtx]) {\n            if (nbr == parent) {\n                continue; // skip the parent\n            }\n            auto kid = traverse(nbr, vtx);\n            // combine\n            best = max(best, max(res.posiTwoProd * kid.posiMax,\n                                 res.posiMax * kid.posiTwoProd));\n            best = max(best, max(res.negaTwoProd * kid.negMax,\n                                 res.negMax * kid.negaTwoProd));\n            res.best = max(res.best, kid.best);\n            res.posiTwoProd = max(res.posiTwoProd, kid.posiTwoProd);\n            res.posiTwoProd =\n                max(res.posiTwoProd,\n                    max(kid.posiMax * res.posiMax, kid.negMax * res.negMax));\n            res.negaTwoProd = min(res.negaTwoProd, kid.negaTwoProd);\n            res.negaTwoProd =\n                min(res.negaTwoProd,\n                    min(kid.negMax * res.posiMax, kid.posiMax * res.negMax));\n            res.posiMax = max(res.posiMax, kid.posiMax);\n            res.negMax = min(res.negMax, kid.negMax);\n            res.vtxCount += kid.vtxCount;\n        }\n        res.best = max(res.best, best);\n        if (res.vtxCount < 3) {\n            _coins[vtx] = 1;\n        } else {\n            _coins[vtx] = res.best;\n        }\n        return res;\n    }\n\npublic:\n    vector<long long> placedCoins(vector<vector<int>>& edges,\n                                  vector<int>& cost) {\n        const int n = edges.size() + 1;\n        vector<vector<int>> g(n);\n        for (auto& e : edges) { // build the graph adjacency lists\n            int a = e[0], b = e[1];\n            g[a].push_back(b);\n            g[b].push_back(a);\n        }\n        _g = std::move(g);\n        _cost = std::move(cost);\n        _coins.resize(n);\n        auto results = traverse(0, -1);\n        return std::move(_coins);\n    }\n};\n```
['Dynamic Programming', 'C++']