Beats 95% ,  DFS with linear DP
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```\nclass Solution {\n\n\t\tpublic long[] dfs(List<List<Integer>> list, int[] visited, int curr , int[] coins , long[] res) {\n\n\t\t\tvisited[curr]=1;\n\t\t\tlong[] dp = new long[6];\n\n\t\t\t long a=Integer.MIN_VALUE;\n\t\t\t long b=Integer.MIN_VALUE;\n\t\t\t long c=Integer.MIN_VALUE;\n             long d = 0;\n             long e=0;\n              \n            long count=0;\n\t\t\tfor(int ele : list.get(curr))\n\t\t\t{\n                if(visited[ele]==1)\n                {\n                    continue;\n                }\n\t\t\t\tlong[] arr = dfs(list , visited , ele,coins ,res);\n                count+=arr[5];\n\t\t\t\tif(a==Integer.MIN_VALUE && b==Integer.MIN_VALUE && c==Integer.MIN_VALUE && d==0 && e==0)\n\t\t\t\t{\n\t\t\t\t\ta=arr[0];\n\t\t\t\t\tb=arr[1];\n\t\t\t\t\tc=arr[2];\n                    d=arr[3];\n                    e=arr[4];\n\t\t\t\t}\n\t\t\t\telse {\n                    long oa=a;\n                    long ob=b;\n                    long oc=c;\n                    long od=d;\n                    long oe=e;\n                    \n\t\t\t\t\ta=Math.max(arr[0] , oa);\n\t\t\t\t\tb=Math.max((long)Math.max(ob,arr[1]) ,(long)arr[0]*oa);\n                \n                    if(ob==Integer.MIN_VALUE && arr[1] == Integer.MIN_VALUE)\n                    {\n                        c=Integer.MIN_VALUE;\n                    }\n                    else if(ob==Integer.MIN_VALUE)\n                    {\n                        c=Math.max((long)Math.max(oc,arr[2]),(long)arr[1]*oa);    \n                    }\n                    else if(arr[1] == Integer.MIN_VALUE)\n                    {\n                        c=Math.max((long)Math.max(oc,arr[2]),(long)ob*arr[0]);  \n                    }\n                    else\n\t\t\t\t\tc=Math.max((long)Math.max(oc,arr[2]),(long)Math.max((long)ob*arr[0],(long)arr[1]*oa));\n                    \n                    \n                    d=Math.min(d,arr[3]);\n                    \n                    e=Math.max(Math.max(e,arr[4]) , (long)od*arr[3]);\n                    \n\t\t\t\t}\n                \n\t\t\t}\n            \n         \n             dp[3] = Math.min(coins[curr],d);\n            dp[4] = Math.max(e,(long)coins[curr]*d);\n\t\t\tdp[0] = Math.max(coins[curr],a);\n            if(a==Integer.MIN_VALUE)\n            {\n                dp[1] = Math.max(a,b);\n            }\n            else\n\t\t\tdp[1] = Math.max((long)coins[curr]*a , (long)b);\n            \n            \n            if(b==Integer.MIN_VALUE)\n            {\n                dp[2] = Math.max(b,c);\n            }\n            else\n\t\t\tdp[2] = Math.max((long)coins[curr]*b , (long)c);\n            \n            if(count+1<3)\n            {\n                res[curr] = 1;\n            }\n            else\n\t\t\tres[curr] = Math.max(dp[2],0L);\n            \n            res[curr] = Math.max(res[curr] , dp[0]*dp[4]);\n            \n            dp[5] =count+1;\n            \n        \n            \n\n\t\t\treturn dp;\n\n\n\t\t}\n\t\tpublic long[] placedCoins(int[][] e, int[] coins) {\n\n\t\t\tList<List<Integer>> list  =  new ArrayList<>();\n\n\t\t\tint n= coins.length;\n\t\t\tfor(int i=0;i<n;i++)\n\t\t\t{\n\t\t\t\tlist.add(new ArrayList<>());\n\t\t\t}\n\n\t\t\tfor(int i=0;i<e.length;i++)\n\t\t\t{\n\t\t\t\tlist.get(e[i][0]).add(e[i][1]);\n\t\t\t\tlist.get(e[i][1]).add(e[i][0]);\n\t\t\t}\n\t\t\tint[] visited = new int[n];\n\t\t\tint[][] dp = new int[n][3];\n\t\t\tlong[] res = new long[n];\n\t\t\tdfs(list,visited,0 ,coins , res);\n\n\t\t\treturn res;\n\n\n\n\n\t\t}\n\n\n\t}\n\n```
['Java']