Heuristic Merging and Tree Heuristic Merging: A Comprehensive Guide

Core Concepts

Fundamental Knowledge: Heuristic Merging (DSU)

Heuristic algorithms are optimizations based on human experience and intuition. The classic example of heuristic merging is the union-find data structure's union by size/rank technique. When merging two sets, we attach the smaller tree to the root of the larger one. This approach,看似暴力, actually guarantees a time complexity of Θ(n log n). Similar optimizations can be applied to data structures like sets and vectors with comparable complexity analysis.

Heuristic merging represents an elegant brute-force solution that appears straightforward but maintains rigorous time complexity guarantees.

Example Problem: [HNOI2009] Dream Pudding

This problem demonstrates a typical application of set merging. The implementation involves careful handling of iterators and a crucial optimization: STL sets and vectors can be swapped in constant time Θ(1).

//opt=1
if(x == y) continue;
int fx = x, fy = y;
if(size[fx] < size[fy]) {
    for(auto it = data[fx].begin(); it != data[fx].end(); ++it) {
        int v = *it;
        auto prevIt = (it == data[fx].begin()) ? it : std::prev(it);
        if((it == data[fx].begin() || (*prevIt + 1 != *it)) && 
           data[fx].find(v-1) == data[fx].end() && 
           data[fy].find(v-1) != data[fy].end()) {
            segments--;
        }
        auto nextIt = std::next(it);
        if((it == --data[fx].end() || (*it + 1 != *nextIt)) && 
           data[fx].find(v+1) == data[fx].end() && 
           data[fy].find(v+1) != data[fy].end()) {
            segments--;
        }
        color[v] = fy;
        data[fy].insert(v);
    }
    data[fx].clear();
} else {
    for(auto it = data[fy].begin(); it != data[fy].end(); ++it) {
        int v = *it;
        auto prevIt = (it == data[fy].begin()) ? it : std::prev(it);
        if((it == data[fy].begin() || (*prevIt + 1 != *it)) && 
           data[fy].find(v-1) == data[fy].end() && 
           data[fx].find(v-1) != data[fx].end()) {
            segments--;
        }
        auto nextIt = std::next(it);
        if((it == --data[fy].end() || (*it + 1 != *nextIt)) && 
           data[fy].find(v+1) == data[fy].end() && 
           data[fx].find(v+1) != data[fx].end()) {
            segments--;
        }
        color[v] = fx;
        data[fx].insert(v);
    }
    data[fy].clear();
    std::swap(data[fx], data[fy]);
}

Main Focus: Tree Heuristic Merging (DSU on Tree)

Tree heuristic merging addresses subtree statistics problems and offline pair queries. It can be combined with tree dynamic programming and solves certain path statistics problems. Many problems solvable with tree Mo's algorithm or segment tree merging can also be solved with DSU on tree, particularly for queries with varying requirements.

The technique leverages the heuristic merging principle by ensuring smaller subtrees are merged into larger ones. The key is identifying heavy and light children:

1. Recursively process light children, resolve their queries, and clear their information
2. Recursively process the heavy child, resolve queries along the heavy path, but preserve its information
3. Merge information from light children and the current node, then process queries. If the current node is a light child, clear all information; otherwise, retain it

Time complexity analysis shows each node is processed at most Θ(log n) times for light edges and once for the node itself, resulting in overall Θ(n log n) complexity. This approach is highly extensible and can be combined with Θ(log n) data structures.

A general framework for DSU on tree:

/*
definitions:
dfn[x]: DFS entry time for node x
L[x]/R[x]: DFS range for subtree rooted at x
size[x]: Size of subtree rooted at x
heavy[x]: Heavy child of x
*/
//-----------------------------
void dfs_pre(int x) {
    size[x] = 1, dfn[x] = ++ timer, L[x] = timer, V[timer] = x;
    for(int i = head[x]; i; i = edge[i].next) {
        int v = edge[i].to;
        dfs_pre(v);
        size[x] += size[v];
        if(size[v] > size[heavy[x]]) heavy[x] = v;
    }
    R[x] = timer;
}

inline void add_contribution(int x, int delta) {
    // Add/remove contribution of node x
}

void update_subtree(int x, int delta) {
    for(int i = L[x]; i <= R[x]; i++) {
        add_contribution(V[i], delta);
    }
}

void query_node(int x) {
    // Calculate answer for queries at node x
}

void dfs(int x, bool keep) {
    for(int i = head[x]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v != heavy[x]) dfs(v, false);
    }
    if(heavy[x]) dfs(heavy[x], true);
    
    for(int i = head[x]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v != heavy[x]) {
            update_subtree(v, 1);
        }
    }
    
    add_contribution(x, 1);
    query_node(x);
    
    if(!keep) update_subtree(x, -1);
}

int main() {
    // Initialize
    dfs_pre(1);
    dfs(1, false);
    // Output results
    return 0;
}

Example Problems

#1 Tree Requests

This problem involves subtree statistics with depth constraints and varying queries. The solution checks how many characters at a specific depth can form a palindrome (count of characters with odd frequency ≤ 1).

inline void add_contribution(int x, int delta) {
    char_count[depth[x]][value[x] - 'a' + 1] += delta;
}

bool check_palindrome(int d) {
    int odd_count = 0;
    for(int i = 1; i <= 26; i++) {
        odd_count += (char_count[d][i] & 1);
    }
    return odd_count <= 1;
}

#2 Blood Cousins Return

This problem handles different query types for counting distinct strings at each depth. A map is used to maintain counts efficiently.

void add_contribution(int x, int delta) {
    if(delta == 1) {
        occurrence[depth[x]][id[x]]++;
        if(occurrence[depth[x]][id[x]] == 1) {
            distinct_count[depth[x]]++;
        }
    } else {
        if(occurrence[depth[x]][id[x]] == 1) {
            distinct_count[depth[x]]--;
        }
        occurrence[depth[x]][id[x]]--;
    }
}

#3 Arpa's Letter-marked Tree and Mehrdad's Dokhtar-kosh Paths

This problem finds the longest palindrome in each subtree. The solution uses a bitset approach where each path is represented as a bitmask and leverages XOR properties to find matching paths.

void dfs_pre(int x, int parent) {
    size[x] = 1, dfn[x] = ++ timer, L[x] = timer, V[timer] = x;
    for(int i = head[x]; i; i = edge[i].next) {
        int v = edge[i].to;
        mask[v] ^= mask[x];
        depth[v] = depth[x] + 1;
        dfs_pre(v, x);
        size[x] += size[v];
        if(size[v] > size[heavy[x]]) heavy[x] = v;
    }
    R[x] = timer;
}

inline void add_contribution(int x, int delta) {
    max_depth[mask[x]] = (delta == -1) ? -INF : 
                        std::max(max_depth[mask[x]], depth[x]);
}

void query_node(int x) {
    for(int i = 0; i < 22; i++) {
        ans[x] = std::max(ans[x], 
            depth[x] + max_depth[mask[x] ^ (1 << i)] - 2 * depth[x]);
    }
    ans[x] = std::max(ans[x], 
        depth[x] + max_depth[mask[x]] - 2 * depth[x]);
}

#4 [NOIP2016] Daily Running

This problem counts paths meeting specific conditions in each subtree. The solution separates paths by their starting and ending points and uses bucket arrays to count valid configurations.

void add_contribution(int x, int delta) {
    for(auto path : start_paths[x]) {
        if(depth[lca[path]] <= depth[current_root]) {
            start_count[depth[x]] += delta;
        }
    }
    for(auto path : end_paths[x]) {
        if(depth[lca[path]] <= depth[current_root]) {
            end_count[path_length[path] - depth[x] + OFFSET] += delta;
        }
    }
}

void query_node(int x) {
    ans[x] += start_count[depth[x] + weight[x]] + 
              end_count[weight[x] - depth[x] + OFFSET];
}

#5 Tree Statistics

This problem counts intervals crossing each edge. The solution uses complementary counting and maintains segments of continuous 0s and 1s.

inline long long segment_sum(int length) {
    return 1LL * length * (length + 1) / 2;
}

void add_contribution(int x, int delta) {
    if(delta == 1) {
        auto it = zero_segments.lower_bound({x, -INF});
        zero_segments.erase(it);
        int len = (-it->second) - (-it->first) + 1;
        total_zero -= segment_sum(len);
        
        if((-it->first) != x) {
            len = (x - 1) - (-it->first) + 1;
            total_zero += segment_sum(len);
            zero_segments.insert({it->first, -(x - 1)});
        }
        
        if((-it->second) != x) {
            len = (-it->second) - (x + 1) + 1;
            total_zero += segment_sum(len);
            zero_segments.insert({-(x + 1), it->second});
        }
        
        // Update one segments
        if(segment[x-1] && segment[x+1]) {
            // Merge two segments
        }
        // ... (rest of the implementation)
        
        segment[x] = 1;
    } else {
        // Remove contribution
    }
}

Additional Practice Problems

• Tree and Queries
• Counting Colors on Trees
• Dominant Indices