https://www.acwing.com/blog/content/30363/

#include <bits/stdc++.h>
using namespace std;

typedef struct Node {
    bool isLeaf;
    char c;
    int v;
    struct Node* lchild;
    struct Node* rchild;
    Node(char c, int v, bool isLeaf) {
        this->c = c;
        this->v = v;
        this->isLeaf = isLeaf;
        this->lchild = NULL;
        this->rchild = NULL;
    }
}HTree,HNode;

int table[27];
int res;

struct compare {
    bool operator()(HTree* a, HTree* b) {
        return a->v > b->v; // 这里定义了最小堆
    }
};
priority_queue<HTree*, vector<HTree*>, compare> pq_min;

void dfs(HTree* cur,int deep) {
    if(cur == NULL) return;
    if(cur->isLeaf == true) {
        res += deep * cur->v;
        return;
    }
    if(cur->lchild) dfs(cur->lchild, deep + 1);
    if(cur->rchild) dfs(cur->rchild, deep + 1);
}

int main() {
    string s;
    cin >> s;

    for(auto c:s) {
        table[c - 'a'] ++;
    } 

    for(int i = 0; i <= 26 && table[i] != 0; i ++) {
        // cout << table[i] << " ";
        pq_min.push(new HNode(i + 'a', table[i], true));
    }
    // cout << pq_min.size();
    HTree* c = NULL;
    while(pq_min.size() >= 2) {
        HNode* a = pq_min.top();
        pq_min.pop();
        HNode* b = pq_min.top();

        pq_min.pop();
        c = new HNode('0',0,false);
        c->lchild = a;
        c->rchild = b;
        c->v = a->v + b->v;
        // printf("from [%c-%d] and [%c-%d] build\n",a->c,a->v,b->c,b->v);
        pq_min.push(c);
    }
    dfs(c, 0);
    cout << res;
}