Small to Large Merging on Trees
IntuitionFirst things first, their are two candidates which can maximise the answer for a node, one is we can take product of three largest values in the subtre
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst things first, their are two candidates which can maximise the answer for a node, one is we can take product of three largest values in the subtree or second we can take product of two smallest negative values with largest positive value in the subtree.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHaving said that we somehow just need to maintain these 5 values for each node. We can use a set preferably multiset because there can be duplicate values. Thus we will maintain a multiset for each node and will merge it with incoming multisets from immediate children in the dfs call. Now here comes the magic of this technique, we will use small to large merging to merge two sets optimally, similar to the merge operation of Union Find. This will ensure that each element is moved atmost LogN time.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    0(NLogN*LogN)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n    private MultiTreeSet<Integer> smallToLargeMerging(MultiTreeSet<Integer> a, MultiTreeSet<Integer> b) {\n        if (a.size() < b.size()) {\n            MultiTreeSet<Integer> temp = a;\n            a = b;\n            b = temp;\n        }\n        while (!b.isEmpty()) {\n            a.add(b.first());\n            b.remove(b.first());\n        }\n        return a;\n    }\n\n    private MultiTreeSet<Integer> dfs(int child, int parent, List<List<Integer>> adj, long[] res, int[] cost) {\n        MultiTreeSet<Integer> ms = new MultiTreeSet<>();\n        ms.add(cost[child]);\n        for (int each : adj.get(child)) {\n            if (each == parent) continue;\n            MultiTreeSet<Integer> curr = dfs(each, child, adj, res, cost);\n            ms = smallToLargeMerging(ms, curr);\n        }\n        if (ms.size() < 3) {\n            res[child] = 1;\n        } else if (ms.size == 3) {\n            int c = ms.last();\n            ms.remove(c);\n            int d = ms.last();\n            ms.remove(d);\n            int e = ms.last();\n            ms.remove(e);\n            for (int it : new int[]{c, d, e}) {\n                ms.add(it);\n            }\n            res[child] = Math.max(0, (long) c * d * e);\n        } else if (ms.size == 4) {\n            int c = ms.last();\n            ms.remove(c);\n            int d = ms.last();\n            ms.remove(d);\n            int e = ms.last();\n            ms.remove(e);\n            int f = ms.last();\n            ms.remove(f);\n            for (int it : new int[]{c, d, e, f}) {\n                ms.add(it);\n            }\n            res[child] = Math.max(0, Math.max((long) c * d * e, (long) c * e * f));\n        } else {\n            int a = ms.first();\n            ms.remove(a);\n            int b = ms.first();\n            ms.remove(b);\n            int c = ms.last();\n            ms.remove(c);\n            int d = ms.last();\n            ms.remove(d);\n            int e = ms.last();\n            ms.remove(e);\n            for (int it : new int[]{a, b, c, d, e}) {\n                ms.add(it);\n            }\n            res[child] = Math.max(0, Math.max((long) c * d * e, (long) c * a * b));\n        }\n        return ms;\n    }\n\n    public long[] placedCoins(int[][] edges, int[] cost) {\n        int n = cost.length;\n        List<List<Integer>> adj = new ArrayList<>();\n        for (int i = 0; i < n; ++i) adj.add(new ArrayList<>());\n        for (int[] each : edges) {\n            int u = each[0], v = each[1];\n            adj.get(u).add(v);\n            adj.get(v).add(u);\n        }\n        long[] res = new long[n];\n        dfs(0, -1, adj, res, cost);\n        return res;\n    }\n}\n\nclass MultiTreeSet<E> {\n    TreeMap<E, Integer> freqTreeMap = new TreeMap<E, Integer>();\n    int size;\n\n    public MultiTreeSet() {\n    }\n\n    public MultiTreeSet(Collection<? extends E> c) {\n        for (E element : c)\n            add(element);\n    }\n\n\n    public int size() {\n        return size;\n    }\n\n    public void add(E element) {\n        Integer freq = freqTreeMap.get(element);\n        if (freq == null)\n            freqTreeMap.put(element, 1);\n        else\n            freqTreeMap.put(element, freq + 1);\n        ++size;\n    }\n\n    public void remove(E element) {\n        Integer freq = freqTreeMap.get(element);\n        if (freq != null) {\n            if (freq == 1)\n                freqTreeMap.remove(element);\n            else\n                freqTreeMap.put(element, freq - 1);\n            --size;\n        }\n    }\n\n\n    public int get(E element) {\n        Integer freq = freqTreeMap.get(element);\n        if (freq == null)\n            return 0;\n        return freq;\n    }\n\n    public boolean contains(E element) {\n        return get(element) > 0;\n    }\n\n    public boolean isEmpty() {\n        return size == 0;\n    }\n\n    public E first() {\n        return freqTreeMap.firstKey();\n    }\n\n    public E last() {\n        return freqTreeMap.lastKey();\n    }\n\n    public E ceiling(E element) {\n        return freqTreeMap.ceilingKey(element);\n    }\n\n    public E floor(E element) {\n        return freqTreeMap.floorKey(element);\n    }\n\n    public E higher(E element) {\n        return freqTreeMap.higherKey(element);\n    }\n\n    public E lower(E element) {\n        return freqTreeMap.lowerKey(element);\n    }\n}\n```
['Depth-First Search', 'Union Find', 'Ordered Set', 'Java']