✅✅ DFS || C++ || Solution with Explanation ✅✅
Intuition\nComputing the optimal coin placement that satisfies the constraints by dynamic programming, using DFS and multisets to track the candidate coin value
# Intuition\nComputing the optimal coin placement that satisfies the constraints by dynamic programming, using DFS and multisets to track the candidate coin values available at each node vector returns the final result.\n\n# Approach\nWe have to find the maximum number of coins that can be placed on the nodes of a tree, with the following constraints:\n\n1. Each node can have at most 3 coins.\n\n2. The value of coins on each node must be distinct.\n\n3. The value of a coin is the absolute value of the cost of that node.\n\n\nMaintains two multisets (pos and neg) at each node to track the distinct positive and negative costs.\n\nDuring DFS, it propagates these sets upwards towards the root.\n\nLimits the size of pos and neg to 3 each, discarding extra elements.\n\nAt each node, it tries all combinations of taking 3 values from pos and 2 values from neg, taking the max as the number of coins at that node. \n# Complexity\n- Time complexity : O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity : O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\nprivate:\n    vector<vector<int>> edge;\n    multiset<int> pos[100005];\n    multiset<int, greater<int>> neg[100005];\n    vector<long long> coins;\n\n    function<void(int, int, const vector<int>&)> dfs = [&](int x, int p, const vector<int>& cost) -> void {\n        if (cost[x] > 0) {\n            pos[x].insert(cost[x]);\n        } else {\n            neg[x].insert(cost[x]);\n        }\n        for (auto y : edge[x]) {\n            if (y == p) continue;\n            dfs(y, x, cost);\n            for (auto i : pos[y]) {\n                pos[x].insert(i);\n            }\n            for (auto i : neg[y]) {\n                neg[x].insert(i);\n            }\n            while ((int)pos[x].size() > 3) pos[x].erase(pos[x].begin());\n            while ((int)neg[x].size() > 3) neg[x].erase(neg[x].begin());\n        }\n        int ps = (int)pos[x].size(), ns = (int)neg[x].size();\n        if (ps + ns < 3) {\n            coins[x] = 1;\n        } else {\n            long long mx = -9e18;\n            if (ps >= 3) {\n                auto itr = pos[x].rbegin();\n                int lst = *itr;\n                itr++;\n                int slst = *itr;\n                itr++;\n                int tlst = *itr;\n                mx = max(mx, 1LL * lst * slst * tlst);\n            }\n            if (ns >= 2 && ps >= 1) {\n                auto itr = neg[x].rbegin();\n                int lst = *itr;\n                itr++;\n                int slst = *itr;\n                int tlst = *pos[x].rbegin();\n                mx = max(mx, 1LL * lst * slst * tlst);\n            }\n            if (mx > 0) {\n                coins[x] = mx;\n            }\n        }\n    };\n\npublic:\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = cost.size();\n        edge.resize(n);\n        coins.resize(n);\n\n        for (auto i : edges) {\n            int u = i[0], v = i[1];\n            edge[u].push_back(v);\n            edge[v].push_back(u);\n        }\n\n        dfs(0, -1, cost);\n        return coins;\n    }\n};\n```
['Depth-First Search', 'C++']