Mat dekho is ques ko || Sirf bohut sara code hai aur kuch nhi
Intuition\n Describe your first thoughts on how to solve this problem. \n3 dfs chalao: \n1) Dfs to calculate the three highest values in subtree of every node\n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n3 dfs chalao: \n1) Dfs to calculate the three highest values in subtree of every node\n2) Dfs to calculate the two lowest values in subtree of every node\n3) Dfs to calculate the number of chhildren of every node \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nIf no of children <3 us ki value 1\nelse take product of three biggest \n    and product of two smallest and one biggest;\n    if( max of the two ) < 0 ==>  value =0;\n    else value=max of the two values\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(3N) :  O(N) for each traversal\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(3N)\n# Code\n```\n#define ll long long\nclass Node{\n    public:\n    long long a,b,c;\n    Node(long long x,long long y,long long z)\n    {\n        a=x; b=y; c=z;\n    }\n};\nclass Node2{\n    public:\n    long long a,b;\n    Node2(long long x,long long y)\n    {\n        a=x; b=y;\n    }\n};\nclass Solution {\npublic:\n\n    Node* solve(int node,vector<int> adj[],vector<int>& cost,vector<int>& vis,map<int,Node*>& vec){\n        ll x=cost[node],y=-10001,z=-10001;\n        vis[node]=1;\n        // return new Node(x,y,z);\n\n        for(auto xx: adj[node]){\n            if(!vis[xx]){\n                Node* f=solve(xx,adj,cost,vis,vec);\n                multiset<ll> st;\n                st.insert(f->a);\n                st.insert(f->b);\n                st.insert(f->c);\n                st.insert(x);\n                st.insert(y);\n                st.insert(z);\n                x=*st.rbegin();\n                st.erase(st.find(x));\n                y=*st.rbegin();\n                st.erase(st.find(y));\n                z=*st.rbegin();\n                st.erase(st.find(z));\n            }\n        }\n        vec[node] = new Node(x,y,z);\n        // cout<<1<<endl;\n        // return new);\n        return vec[node];\n    } \n\n    Node2* solve2(int node,vector<int> adj[],vector<int>& cost,vector<int>& vis,map<int,Node2*>& vec2){\n        ll x=cost[node],y=10001;\n        vis[node]=1;\n\n        for(auto xx: adj[node]){\n            if(!vis[xx]){\n                Node2* f=solve2(xx,adj,cost,vis,vec2);\n                multiset<ll> st;\n                st.insert(f->a);\n                st.insert(f->b);\n                st.insert(x);\n                st.insert(y);\n                x=*st.begin();\n                st.erase(st.find(x));\n                y=*st.begin();\n                st.erase(st.find(y));\n            }\n        }\n\n        vec2[node] = new Node2(x,y);\n        return vec2[node];\n    }\n    int dfs(int node,vector<int> adj[],vector<int>& children,vector<int>& vis){\n        int child=0;\n        vis[node]=1;\n        for(auto x: adj[node]){\n            if(!vis[x]){\n                child+=dfs(x,adj,children,vis);\n            } \n        }\n        children[node]=child+1;\n        return child+1;\n    }\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n=cost.size();\n        vector<int> children(n,0);\n        vector<int> adj[n];\n        for(auto edge: edges)\n        {\n            adj[edge[0]].push_back(edge[1]);\n            adj[edge[1]].push_back(edge[0]);\n        }\n        vector<int> vis(n,0);\n        dfs(0,adj,children,vis);\n        // for(auto xx:  children) cout<<xx<<" ";\n        // cout<<endl;\n        // return children;\n        // vis(n,0);\n        for(int i=0;i<n;i++) vis[i]=0;\n        // vector<Node*> vec1;\n        map<int,Node*> vec;\n\n        // vector<Node2*> vec2;\n        map<int,Node2*> vec2;\n        solve(0,adj,cost,vis,vec);\n        for(int i=0;i<n;i++) vis[i]=0;\n        \n        solve2(0,adj,cost,vis,vec2);\n\n        // return {vec2[0]->a};\n        // return {0};\n        vector<ll> res(n,0);\n        for(int i=0;i<n;i++){\n            if(children[i]>=3){\n                Node* node= vec[i];\n                Node2* node2 = vec2[i];\n                ll x= (node->a)*(node->b)*(node->c);\n                ll y= (node->a)*(node2->a)*(node2->b);\n                if(max(x,y)<0) res[i]=0;\n                else res[i]=max(x,y);\n            }\n            else res[i]=1;\n        }\n        return res;\n    }\n};\n```
['C++']