c++ traversal
\nclass Solution {\npublic:\n    \n    #define ll long long\n    \n    vector<vector<int>> m;\n    vector<int> cost;\n    vector<ll> ans;\n    int n;\n    vecto
```\nclass Solution {\npublic:\n    \n    #define ll long long\n    \n    vector<vector<int>> m;\n    vector<int> cost;\n    vector<ll> ans;\n    int n;\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        this->n = cost.size();\n        this->m = vector<vector<int>>(n, vector<int>());\n        this->cost = cost;\n        this->ans = vector<ll>(n, -1);\n        for (auto& v : edges) {\n            m[v[0]].push_back(v[1]);\n            m[v[1]].push_back(v[0]);\n        }\n        \n        traverse(0, -1);\n        for (int i = 0; i < n; i++) ans[i] = max(ans[i], 0LL);\n        return ans;\n        \n    }\n    \n    vector<int> traverse(int curr, int par) {\n        vector<int> val;\n        int children = 0;\n        for (int i : m[curr]) {\n            if (i != par) {\n                vector<int> next = traverse(i, curr);\n                children += next[0];\n                for (int k = 1; k < next.size(); k++) val.push_back(next[k]);\n            }\n        }\n        \n        val.push_back(cost[curr]);\n        sort(val.begin(), val.end());\n        \n        if (val.size() < 3) {\n            ans[curr] = 1LL;\n            vector<int> ret;\n            ret.push_back(children + 1);\n            for (int i : val) ret.push_back(i);\n            return ret;\n        }\n        \n        if (val.size() == 3) {\n            ans[curr] = 1LL * val[0] * val[1] * val[2];\n            return {children + 1, val[0], val[1], val[2]};\n        }\n        \n        ans[curr] = max(1LL * val[0] * val[1] * val.back(), 1LL * val.back() * val[val.size() - 2] * val[val.size() - 3]);\n        if (val.size() == 4) return {children + 1, val[0], val[1], val[2], val[3]};\n        return {children + 1, val[0], val[1], val[val.size() - 3], val[val.size() - 2], val.back()};\n        \n        \n        \n        \n    }\n    \n};\n```
['Depth-First Search', 'C']