Merge sort (No priority queue)
Intuition\n Describe your first thoughts on how to solve this problem. \nTo keep track of 3 max values and 3 min values in each node where do not need to use pr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo keep track of 3 max values and 3 min values in each node where do not need to use priority queue. Instead using merge procedure of merge sort to always get these 6 values in each node.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> mn_3;\n    vector<vector<int>> mx_3;\n    vector<vector<int>> g;\n    vector<long long> ans;\n    int n;\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        n = cost.size(); \n        g = vector<vector<int>>(n);\n        ans.resize(n);\n        mn_3.resize(n);\n        mx_3.resize(n);\n        for (auto &e : edges) {\n            g[e[0]].push_back(e[1]);\n            g[e[1]].push_back(e[0]);\n        }\n        dfs(0, -1, cost);   \n        return ans;\n    }\n    void dfs(int u, int par, vector<int> &cost) {\n        mn_3[u].push_back(cost[u]);\n        mx_3[u].push_back(cost[u]);\n        for (auto &v : g[u]) {\n            if (v != par) {\n                dfs(v, u, cost);\n                merge(mn_3[v], mn_3[u], 0);\n                merge(mx_3[v], mx_3[u], 1);\n            }\n        }\n        long long ans_u;\n        if (mn_3[u].size() < 3) ans_u = 1;\n        else {\n            ans_u = max(1LL*mx_3[u][2]*mx_3[u][1]*mx_3[u][0], 1LL*mn_3[u][0]*mn_3[u][1]*mx_3[u][0]);\n            if (ans_u < 0) ans_u = 0;\n        }\n        ans[u] = ans_u;\n    }\n    void merge(vector<int> &mn_3, vector<int> &cur, int mode) {\n        vector<int> res;\n        int i = 0;\n        int j = 0;\n        while (i < mn_3.size() && j < cur.size() && res.size() < 3) {\n            if (mode == 0) {\n                if (mn_3[i] <= cur[j]) {\n                    res.push_back(mn_3[i]);\n                    i++;\n                } else {\n                    res.push_back(cur[j]);\n                    j++;\n                }\n            } else {\n                if (mn_3[i] >= cur[j]) {\n                    res.push_back(mn_3[i]);\n                    i++;\n                } else {\n                    res.push_back(cur[j]);\n                    j++;\n                }\n            }\n        }\n        if (res.size() == 3) {\n            cur = res;\n            return;\n        }\n        while (i < mn_3.size() && res.size() < 3) {\n            res.push_back(mn_3[i]);\n            i++;\n        }\n        while (j < cur.size() && res.size() < 3) {\n            res.push_back(cur[j]);\n            j++;\n        }\n        cur = res;\n    }\n};\n```
['C++']