This article presents concise, robust solutions to two distinct algorithmic problems from a competitive programming context: parsing and decoding HTTP-like header structures using Huffman tree reconstruction, and computing the minimum excluded value (MEX) on tree paths via persistent segment trees.

HTTP Header Decoding with Huffman Reconstruction

The first problem involves reconstructing a Huffman-encoded binary tree from a compact string representation, then using it to decode header field values. The encoding uses '0' for internal nodes and '1' for leaves, followed by ASCII characters. A depth-first recursive parser builds the tree, and a traversal populates a lookup map from bitstring paths to decoded characters.

Header fields are stored in two tiers: static entries (indexed 1 to s) and a sliding cache of dynamic entries (bounded by size d). Each query either retrieves a field by index or inserts a new one — with optional hex-to-binary expansion and Huffman decoding applied to both key and value if prefixed with "HH".

Key implementation notes:

• Uses std::deque for O(1) front insertion and back eviction in the dynamic entry cache.
• Hex decoding handles lowercase a–f and digits; pads each nibble to 4 bits, then strips trailing bits as specified.
• Huffman decoding walks the bitstream left-to-right, matching prefixes against the precomputed map.

struct HuffmanNode {
    char symbol = '\0';
    std::shared_ptr<HuffmanNode> left, right;
    HuffmanNode(char c) : symbol(c) {}
    HuffmanNode() = default;
};

std::shared_ptr<HuffmanNode> buildTree(const std::string& enc, int& i) {
    if (i >= enc.size()) return nullptr;
    if (enc[i] == '1') {
        ++i;
        return std::make_shared<HuffmanNode>(enc[i++]);
    } else if (enc[i] == '0') {
        ++i;
        auto node = std::make_shared<HuffmanNode>();
        node->left = buildTree(enc, i);
        node->right = buildTree(enc, i);
        return node;
    }
    return nullptr;
}

std::unordered_map<std::string, char> buildCodeMap(const std::shared_ptr<HuffmanNode>& root) {
    std::unordered_map<std::string, char> codes;
    std::function<void(std::shared_ptr<HuffmanNode>, std::string)> dfs;
    dfs = [&](std::shared_ptr<HuffmanNode> n, std::string path) {
        if (!n) return;
        if (n->symbol != '\0') {
            codes[path] = n->symbol;
            return;
        }
        dfs(n->left, path + "0");
        dfs(n->right, path + "1");
    };
    dfs(root, "");
    return codes;
}

std::string hexToBinary(const std::string& s) {
    if (s.empty() || s[0] != 'H') return s;
    std::string bin;
    for (size_t i = (s[1] == 'H' ? 2 : 1); i < s.size() - 2; ++i) {
        int val = std::isdigit(s[i]) ? s[i] - '0' : std::tolower(s[i]) - 'a' + 10;
        for (int b = 3; b >= 0; --b) bin += ((val >> b) & 1) ? '1' : '0';
    }
    int trim = s.back() - '0';
    return bin.substr(0, std::max(0, (int)bin.size() - trim));
}

std::string huffmanDecode(const std::string& encoded, const std::unordered_map<std::string, char>& codes) {
    std::string result, prefix;
    for (char b : encoded) {
        prefix += b;
        auto it = codes.find(prefix);
        if (it != codes.end()) {
            result += it->second;
            prefix.clear();
        }
    }
    return result;
}

Path MEX Queries on Trees Using Persistent Segment Trees

The second problem asks for the MEX of values along the simple path between two nodes in a rooted tree. The solution leverages Euler Tour (DFS order) and persistent segment trees to support efficient range MEX queries over arbitrary tree paths.

A standard heavy-light decomposition is used to compute LCA and map tree paths onto contiguous DFS intervals. For each node, a version of the persistent segment tree stores frequency counts of values encountered on the path from root to that node. To answer a MEX query on path u–v, we combine versions at u, v, and subtract contributions from lca(u,v) and its parent — effectively isolating the path’s multiset.

The segment tree supports binary search for the smallest missing non-negative integer: at each level, it compares the count of numbers in the left subtree against the expected size; if the left side is incomplete, the MEX lies there; otherwise, it recurses right.

struct PersistentSegTree {
    struct Node { int ls = 0, rs = 0, cnt = 0; };
    std::vector<Node> t;
    std::vector<int> roots;
    int nodeCount = 0, n;

    PersistentSegTree(int size) : n(size), t(1), roots(size + 1, 0) {}

    void insert(int& u, int prev, int l, int r, int pos) {
        u = ++nodeCount;
        t.push_back(t[prev]);
        t[u].cnt = t[prev].cnt + 1;
        if (l == r) return;
        int mid = (l + r) / 2;
        if (pos <= mid) {
            insert(t[u].ls, t[prev].ls, l, mid, pos);
        } else {
            insert(t[u].rs, t[prev].rs, mid + 1, r, pos);
        }
    }

    int queryMEX(int u, int v, int p, int gp, int l, int r) const {
        if (l == r) return (t[u].cnt + t[v].cnt - t[p].cnt - t[gp].cnt) ? l + 1 : l;
        int mid = (l + r) / 2;
        int leftCnt = t[t[u].ls].cnt + t[t[v].ls].cnt - t[t[p].ls].cnt - t[t[gp].ls].cnt;
        int expectedLeft = mid - l + 1;
        if (leftCnt < expectedLeft) {
            return queryMEX(t[u].ls, t[v].ls, t[p].ls, t[gp].ls, l, mid);
        } else {
            return queryMEX(t[u].rs, t[v].rs, t[p].rs, t[gp].rs, mid + 1, r);
        }
    }
};