DFS , avoid sorting all childs by carry on max3 and min2
Intuition\n Describe your first thoughts on how to solve this problem. \nAfter spent hours on this single problem, I wont call this problem an easy one even tho
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAfter spent hours on this single problem, I won`t call this problem an easy one even though the logic seems easy at first glance, I will very likely fail if I met this problem again in real interview no matter how many times I practice leetcode.\n\nFirst, It`s tricky to build the tree, the edges have no directioin so you need to cancel the other direction when you know you have right direction.\n\nSecond, the subproblem is tricky, finding maxProduct from list of integer, I used comparision directly, keeping the max3 and min2 in the node will be helpful for access them when needed.\n\nThird, you`ll likely get TLE if simply sort them, the trick here is not to sort all the childs, instead, keep a record of all the max3 and min2 and merge them in parent node.\n\nPaste my passed code here just to memorize those precious hours I spent in this problem.\n\n# Code\n```\nclass Solution {\n    class Node {\n        int n;\n        int cost;\n        List<Node> childs=new ArrayList<>();\n        public List<Node> max3=new ArrayList<>();\n        public List<Node> min2=new ArrayList<>();\n        public void addChild(Node c){\n            childs.add(c);\n        }\n\n        public void updateMax3(Node c){\n            if(max3.size()<3){\n                max3.add(c);\n                sort3(max3);\n            }else{\n                boolean found=false;\n                if(c.cost>max3.get(0).cost){\n                    max3.set(0,c);\n                    found=true;\n                }\n                else if(c.cost>max3.get(1).cost){\n                    max3.set(1,c);\n                    found=true;\n                }\n                else if(c.cost>max3.get(2).cost){\n                    max3.set(2,c);\n                    found=true;\n                };\n                if(found){\n                    sort3(max3);\n                }\n            }\n        }\n\n        public void updateMin2(Node c){\n            if(min2.size()<2){\n                min2.add(c);\n                if(min2.size()==2&&min2.get(0).cost>min2.get(1).cost)swap(min2,0,1);\n            }else{\n                boolean found=false;\n                if(c.cost<min2.get(1).cost){\n                    min2.set(1,c);\n                    found=true;\n                }else if(c.cost<min2.get(0).cost){\n                    min2.set(0,c);\n                    found=true;\n                }\n                if(found){\n                    if(min2.get(0).cost>min2.get(1).cost)swap(min2,0,1);\n                }\n            }\n        }\n\n        public Node(int num,int cost,List<Node> childs){\n            this.n=num;\n            this.cost=cost;\n            this.childs=childs;\n            max3.add(this);\n            min2.add(this);\n        }\n\n        @Override \n        public String toString(){\n            return "node"+n+"cost"+cost;\n        }\n        private void sort3(List<Node> l){\n            if(l.size()<3)return;\n            if(l.get(0).cost>l.get(1).cost)swap(l,0,1);\n            if(l.get(1).cost>l.get(2).cost)swap(l,1,2);\n            if(l.get(0).cost>l.get(1).cost)swap(l,0,1);\n        }\n        private void swap(List<Node> l, int a, int b){\n            Node k=l.get(a);\n            l.set(a,l.get(b));\n            l.set(b,k);\n        }\n\n        public long getCoin(){\n            if(max3.size()<3)return 1;\n            long res=0;\n            int n=childs.size();\n            sort3(max3);\n            if(min2.get(0).cost>min2.get(1).cost)swap(min2,0,1);\n            res=Math.max(res,1l*max3.get(0).cost*max3.get(1).cost*max3.get(2).cost);\n            res=Math.max(res,1l*max3.get(2).cost*min2.get(0).cost*min2.get(1).cost);\n            return res;\n        }\n    }\n    Node[] nodes;\n    long[] coin;\n    long[] cost;\n    Map<Integer,Set<Integer>> m=new HashMap<>();\n    public long[] placedCoins(int[][] edges, int[] cost) {\n        nodes=new Node[cost.length];\n        coin=new long[cost.length];\n        this.cost=new long[cost.length];\n        for(int i=0;i<nodes.length;i++){\n            nodes[i]=new Node(i,cost[i],new ArrayList<Node>());\n        }\n        for(int[] e:edges){\n            int a=e[0],b=e[1];\n            m.putIfAbsent(a,new HashSet<Integer>());\n            m.putIfAbsent(b,new HashSet<Integer>());\n            m.get(a).add(b);\n            m.get(b).add(a);\n        }\n        build(0);\n        System.out.println("donebuild");\n        find(nodes[0]);\n        return coin;\n    }\n\n    private void build(int r){\n        Set<Integer> next=new HashSet<>();\n        for(int i:m.get(r)){\n                next.add(i);\n                nodes[r].addChild(nodes[i]);\n        }\n        for(int n:next){\n            m.get(n).remove(r);\n        }\n        for(int n:next)build(n);\n\n    }\n\n    private Node find(Node root){\n        if(root==null)return null;\n        for(Node c:root.childs){\n            Node k=find(c);\n            if(k==null)continue;\n            for(Node t:k.max3){\n                root.updateMax3(t);\n            }\n            for(Node t:k.min2){\n                root.updateMin2(t);\n            }\n        }\n        \n        coin[root.n]=root.getCoin();\n        // System.out.println("root:"+root+",max3:"+root.max3+",min2:"+root.min2+",coin:"+coin[root.n]);\n        return root;\n    }\n\n\n}\n\n//          0\n//   2            6\n//            7       3\n//                 1      9   5\n//              4    8   \n```
['Java']