Huffman Codes 非建树

In 1953, David A. Huffman published his paper “A Method for the Construction of Minimum-Redundancy Codes”, and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string “aaaxuaxz”, we can observe that the frequencies of the characters ‘a’, ‘x’, ‘u’ and ‘z’ are 4, 2, 1 and 1, respectively. We may either encode the symbols as {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}, or in another way as {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}, both compress the string into 14 bits. Another set of code can be given as {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}, but {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} is NOT correct since “aaaxuaxz” and “aazuaxax” can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.

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

int n;
unordered_map<char, int> cnt;

int main() 
{
   
#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    cin >> n;
    priority_queue<int, vector<int>, greater<int> > q;

    int val = 0;

    for (int i = 0; i < n; ++ i) {
   
        char c;
        int t;
        cin >> c >> t;
        cnt[c] = t;

        q.push(t);
    }

    while (q.size() > 1) {
   
        int a = q.top(); q.pop();
        int b = q.top(); q.pop();
        val += a + b;
        //精华所在，每个叶子节点权值被加的次数等于它的深度
        q.push(a + b);
    }
    
    int kase;
    cin >> kase;
    
    while (kase -- ) {
   
        unordered_map<string, bool> m;
        bool flag = true;   //记录是否有相同编码出现
        int sum = 0;

        for (int i = 0; i < n; ++ i) {
   
            char c; string s;
            cin >> c >> s;

            if (m[s])
                flag = false;
            
            for (int i = 0; i <= s.size(); ++i) {
   
                m[s.substr(0, i)] = true;
            }
            
            sum += cnt[c] * s.length();
        }

        if (sum == val and flag)
            printf("Yes\n");
        else {
   
            printf("No\n");
        }
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}