Skip to content

Combining Techniques

Combining primitives: sieve + ancestor stack, Euler tour + BIT, HLD + frequency map

Why This Lesson Exists

Every technique you've learned in this course is a primitive. Postorder DFS, Euler tours, binary lifting, rerooting, segment trees, HLD, centroid decomposition, DSU on tree — each solves a clean, isolated problem.

Real contest problems aren't clean or isolated. The hard ones require you to recognize two or three primitives hiding inside one problem statement, then wire them together.

This lesson presents three such problems. For each, we walk through the thinking process: read the problem, identify the sub-problems, match each to a technique, and combine.

Problem 1: Nearest Prime Ancestor

Statement: You have a rooted tree where each node holds a positive integer value. For each node \(v\), find the nearest ancestor \(u\) (possibly \(v\) itself) such that \(\text{value}(u)\) is prime. If no such ancestor exists, output \(-1\).

Constraints: \(n \leq 10^5\), values \(\leq 10^6\).

Thinking Process

What sub-problems do you see?

  1. Check whether a value is prime → sieve of Eratosthenes (precompute).
  2. For each node, find the nearest ancestor satisfying a condition → DFS with an ancestor stack (Ch 10).

How do they compose?

Run a sieve up to \(10^6\) first. Then DFS the tree, maintaining a stack of ancestors whose values are prime. When entering a node: - If its value is prime, push it onto the stack. - The answer for this node is the stack's top (the nearest prime ancestor).

When leaving a node, pop it from the stack if you pushed it.

The Code

void buildSieve() {
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; (long long)i * i < MAXVAL; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < MAXVAL; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

void dfs(int node, int parentNode, vector<int>& primeAncestorStack) {
    bool pushed = false;
    if (isPrime[nodeValue[node]]) {
        primeAncestorStack.push_back(node);
        pushed = true;
    }

    if (!primeAncestorStack.empty()) {
        answer[node] = primeAncestorStack.back();
    } else {
        answer[node] = -1;
    }

    for (int neighbor : adj[node]) {
        if (neighbor == parentNode) continue;
        dfs(neighbor, node, primeAncestorStack);
    }

    if (pushed) {
        primeAncestorStack.pop_back();
    }
}

Complexity: \(O(V_{\max} \log \log V_{\max})\) for the sieve + \(O(n)\) for the DFS = \(O(n + V_{\max} \log \log V_{\max})\).

Techniques composed: Sieve (number theory) + ancestor stack DFS (tree traversal).

Problem 2: Sum of Distances with Point Updates

Statement: You have a rooted tree with node values. Support two operations: 1. Update: Change the value of node \(v\) to \(x\). 2. Query: What is the sum of \(\text{value}(u) \cdot \text{dist}(u, \text{root})\) over all nodes \(u\)?

Equivalently: each node contributes its value times its depth to the total. When a value changes, the total changes.

Constraints: \(n \leq 10^5\), \(q \leq 10^5\).

Thinking Process

What sub-problems do you see?

  1. The answer is \(\sum_{u} \text{value}(u) \cdot \text{depth}(u)\). Each node's contribution is independent. An update to node \(v\) changes the total by \((\text{newValue} - \text{oldValue}) \cdot \text{depth}(v)\).

Wait — that's just a single variable tracking the sum. An update changes it in \(O(1)\). No fancy data structure needed.

But what if the query is harder: "sum of distances from node \(v\) to all other nodes" (not just the root)? Now you need rerooting.

Harder version: "After updates, query the sum of \(\text{value}(u) \cdot \text{dist}(u, v)\) for any query node \(v\)."

Now the sub-problems are:

  1. Flatten the tree with an Euler tour so subtree sums are range queries.
  2. Maintain weighted sums using a BIT — one BIT for \(\sum \text{value}(u)\) and another for \(\sum \text{value}(u) \cdot \text{depth}(u)\).
  3. Rerooting formula (Ch 9) to shift the answer from root to any node \(v\).

The distance from \(v\) to all nodes can be decomposed:

\[\sum_u \text{value}(u) \cdot \text{dist}(u, v) = \sum_u \text{value}(u) \cdot (\text{depth}(u) + \text{depth}(v) - 2 \cdot \text{depth}(\text{LCA}(u,v)))\]

For a fixed query node \(v\), this splits into three terms involving subtree sums along the path from root to \(v\). Each can be answered with the BIT over the Euler tour.

The Code (Simplified: Distance-from-Root Version)

void dfs(int node, int parentNode, int dep) {
    depthNode[node] = dep;
    totalWeightedDepth += (long long)nodeValue[node] * dep;

    for (int neighbor : adj[node]) {
        if (neighbor == parentNode) continue;
        dfs(neighbor, node, dep + 1);
    }
}

// Update: change value of targetNode
totalWeightedDepth += (long long)(newValue - nodeValue[targetNode]) * depthNode[targetNode];
nodeValue[targetNode] = newValue;

// Query: return totalWeightedDepth

Techniques composed: Euler tour + BIT (Ch 11) + rerooting formula (Ch 9) for the general version.

Problem 3: Distinct Colors on a Path

Statement: Given a tree where each node has a color, answer queries: "How many distinct colors are on the path from \(u\) to \(v\)?"

Constraints: \(n \leq 10^5\), \(q \leq 10^5\).

Thinking Process

What sub-problems do you see?

  1. Path decomposition — we need to process a path from \(u\) to \(v\). That screams HLD.
  2. Distinct counting on a range — segment trees handle sum/max/min, but distinct counting is harder. A segment tree can't easily merge "distinct count on left half" with "distinct count on right half."

This is where two techniques collide: HLD gives you the path as \(O(\log n)\) array ranges, but distinct counting on array ranges requires something like Mo's algorithm or persistent segment trees.

Approach 1: HLD + Mo's algorithm on trees.

Flatten the tree with HLD. Use Mo's algorithm to answer range queries for distinct counts. This gives \(O((n + q) \sqrt{n})\).

Approach 2: Offline with Euler tour.

If queries are offline, sort them and use a BIT to track the last occurrence of each color. For each position, update the BIT to mark where each color last appeared. A subtree distinct count is then a BIT query.

For paths, combine with LCA: the path from \(u\) to \(v\) passes through \(\text{LCA}(u,v)\). Decompose into the two branches and handle with the BIT approach.

Approach 3: DSU-on-tree style with HLD.

At each chain in HLD, maintain a color frequency map. Merge maps when combining chains along the path. Use small-to-large merging on the maps.

Sketch (HLD + Map Merging)

void dfsSetup(int node, int par, int dep) {
    parentNode[node] = par;
    depthNode[node] = dep;
    subtreeSize[node] = 1;
    heavyChild[node] = -1;
    int maxChildSize = 0;

    for (int neighbor : adj[node]) {
        if (neighbor == par) continue;
        dfsSetup(neighbor, node, dep + 1);
        subtreeSize[node] += subtreeSize[neighbor];
        if (subtreeSize[neighbor] > maxChildSize) {
            maxChildSize = subtreeSize[neighbor];
            heavyChild[node] = neighbor;
        }
    }
}

void decompose(int node, int head) {
    chainHead[node] = head;
    flatPosition[node] = timer;
    flatColor[timer] = nodeColor[node];
    timer++;

    if (heavyChild[node] != -1) decompose(heavyChild[node], head);
    for (int neighbor : adj[node]) {
        if (neighbor == parentNode[node] || neighbor == heavyChild[node]) continue;
        decompose(neighbor, neighbor);
    }
}

int pathDistinctColors(int u, int v) {
    unordered_set<int> colorSet;

    while (chainHead[u] != chainHead[v]) {
        if (depthNode[chainHead[u]] < depthNode[chainHead[v]]) swap(u, v);
        for (int pos = flatPosition[chainHead[u]]; pos <= flatPosition[u]; pos++) {
            colorSet.insert(flatColor[pos]);
        }
        u = parentNode[chainHead[u]];
    }

    if (depthNode[u] > depthNode[v]) swap(u, v);
    for (int pos = flatPosition[u]; pos <= flatPosition[v]; pos++) {
        colorSet.insert(flatColor[pos]);
    }

    return colorSet.size();
}

This is \(O(n \log n)\) per query (walking the chains and inserting into the set). For tighter bounds, replace the set with Mo's algorithm on the flattened array.

Techniques composed: HLD (Ch 14) + frequency tracking (DSU-on-tree style, Ch 14).

The Composition Pattern

Every hard tree problem follows the same decomposition:

  1. Identify the geometry: Is it a path? A subtree? All pairs?
  2. Identify the query type: Aggregate (sum, max)? Counting (distinct, frequency)? Existence?
  3. Match each part to a primitive. The geometry tells you which decomposition (HLD, centroid, Euler tour). The query type tells you which data structure (segment tree, BIT, set, Mo's).
  4. Wire them together. The decomposition produces array ranges. The data structure answers queries on those ranges.

The value of this course is not in memorizing 14 chapters of techniques. It's in recognizing which 2-3 techniques compose to solve the problem in front of you. Every problem is a combination. Once you see the pieces, the implementation follows.

Try It

Pick one of the three problems above and implement it from scratch without looking at the code. Time yourself.

Challenge: Here's a fourth composition problem. "For each node, find the number of nodes in its subtree whose value is a prime AND whose depth is even." Identify the two techniques needed (sieve + Euler tour BIT with a condition filter) and implement it.

Edge Cases to Watch For

  • No prime values in the tree (Problem 1): The prime ancestor stack stays empty throughout the DFS. Every node returns \(-1\). If your code pops from an empty stack without checking, it crashes.
  • All nodes have the same color (Problem 3): Every path has exactly 1 distinct color. The HLD segment tree must correctly handle the "merge two adjacent segments with the same color" case — if the merge logic always adds 1 at chain boundaries, it overcounts.

Problems

Problem Link Difficulty
LC 834 — Sum of Distances in Tree leetcode.com/problems/sum-of-distances-in-tree Hard
CF 600E — Lomsat gelral codeforces.com/contest/600/problem/E Medium
SPOJ COT — Count on a Tree spoj.com/problems/COT Hard
CF 375D — Tree of Science codeforces.com/contest/375/problem/D Hard
CF 342E — Xenia and Tree codeforces.com/problemset/problem/342/E Hard
CF 741D — Arpa's Letter-marked Tree codeforces.com/problemset/problem/741/D Hard
CSES 2080 — Fixed-Length Paths II cses.fi/problemset/task/2080 Hard

What's Next?

You can now decompose any tree problem into primitives and compose them. Chapter 16 (the Appendix) explores the mathematical side: counting trees, isomorphism, and the deep connections between trees and combinatorics.