short rust and c++
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```\nimpl Solution {\n    pub fn dfs(g : &Vec<Vec<i32>>, idx : i32, fa : i32, cost : &Vec<i32>, ans : &mut Vec<i64>) -> Vec<i32>{\n        let mut a : Vec<i32> = vec![cost[idx as usize]];\n        for &child in &g[idx as usize]{\n            if(fa == child){continue};\n            let subtree = Solution::dfs(&g, child, idx,  &cost, ans);\n            a.extend(subtree);\n        }\n        a.sort();\n        let n = a.len();\n        if n >= 3{\n            let x = a[n - 1] as i64 * a[n - 2] as i64 * a[n - 3]as i64;\n            let y = a[n - 1] as i64 * a[0]as i64* a[1] as i64;\n            let tmp : i64 = *[x, y, 0].iter().max().unwrap();\n            ans[idx as usize] = tmp;\n        }\n        if n > 5{\n            let tmp : Vec<i32> = vec![a[0], a[1], a[n - 1], a[n - 2], a[n - 3]];\n            return tmp;\n        }\n        return a;\n        \n    }\n    pub fn placed_coins(edges: Vec<Vec<i32>>, cost: Vec<i32>) -> Vec<i64> {\n        let mut g : Vec<Vec<i32>> = vec![vec![]; 20020];\n        for item in &edges{\n            if let &[u, v] = item.as_slice(){\n                g[u as usize].push(v);\n                g[v as usize].push(u);  \n            };\n        }\n        let mut ans : Vec<i64>= vec![1; cost.len()];\n        Solution::dfs(&g, 0, -1, &cost, &mut ans);\n        return ans\n    }\n}\n```\n# Code\n```\nclass Solution {\npublic:  \n    using ll = long long;\n    vector<ll> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        map<ll, vector<ll>> m;\n        //build graph\n        for(auto v : edges){\n            m[v[0]].push_back(v[1]);\n            m[v[1]].push_back(v[0]);\n        }\n        vector<ll> ret(cost.size(), 1);\n        function<vector<ll>(ll, ll)> dfs;\n        dfs = [&](ll node, ll fa)->vector<ll>{\n            vector<ll> childVal{cost[node]};\n            for(auto child: m[node]){\n                if(child == fa)continue;\n                auto res = dfs(child, node);\n                childVal.insert(childVal.end(), res.begin(), res.end());\n            }\n            sort(childVal.begin(), childVal.end());\n            ll tmp = 0;\n            const ll _n = childVal.size();\n            if(_n >= 3){\n                tmp = max(childVal[0] * childVal[1] * childVal.back()*1LL, tmp);\n                tmp = max(childVal.back() * childVal[_n - 2] * childVal[_n - 3] * 1LL, tmp);\n                ret[node] = tmp;\n            }\n            if(_n > 5){\n                return vector<ll> {childVal[0], childVal[1], childVal[_n - 3], childVal[_n - 2]*1LL ,childVal.back()};\n            }\n            return childVal;\n        };\n        dfs(0, -1);\n        return ret;\n    }\n};\n```\n\n
['C++', 'Rust']