Long-Chain Decomposition (LCD) is a specialized tree decomposition technique. While less common than Heavy-Light Decomposition (HLD), it offers distinct advantages for specific problems, particularly those involving depth-related dynamic programming or k-th ancestor queries.

Core Concepts: Long Sons and Chains

In LCD, for any node u, its long son is defined as the child v that maximizes the depth of the subtree rooted at v. A long chain is formed by recursively following long sons from a node down to a leaf.

The implementation involves two Depth First Search (DFS) passes: one to calculate depths and identify long sons, and another to assign chain tops.

const int MAXN = 100005;

struct Edge {
    int to, next;
} edges[MAXN * 2];
int head[MAXN], cnt;

int depth[MAXN];          // Depth of the node
int max_sub_len[MAXN];    // Length of the longest chain starting from this node
int long_child[MAXN];     // The long son
int top_node[MAXN];       // Top of the current chain

// First DFS: Calculate depths and identify the long son
void calculate_depths(int u, int parent) {
    depth[u] = depth[parent] + 1;
    max_sub_len[u] = 1; // Count the node itself
    int best_depth = -1;
    
    for (int i = head[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (v == parent) continue;
        
        calculate_depths(v, u);
        
        if (max_sub_len[v] > best_depth) {
            best_depth = max_sub_len[v];
            long_child[u] = v;
        }
    }
    max_sub_len[u] = best_depth + 1;
}

// Second DFS: Assign chain tops
void decompose(int u, int chain_top) {
    top_node[u] = chain_top;
    if (!long_child[u]) return; // Leaf node
    
    // Continue the long chain
    decompose(long_child[u], chain_top);
    
    // Start new chains for other children
    for (int i = head[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (v == long_child[u] || v == chain_top) continue;
        decompose(v, v);
    }
}

Key Properties

A crucial property of LCD is that the number of light edges (edges not belonging to a long chain) on the path from any node to the root is bounded by O(√n).

Proof Sketch: Consider moving up the tree. Whenever we traverse a light edge, we move to a sibling subtree whose maximum depth is strictly smaller than the current one. In the worst-case scenario, this results in a structure where chain lengths decrease rapidly, analogous to an arithmetic sequence, leading to the square root bound.

Memory Optimization via DFS Order

Similar to HLD, LCD facilitates information merging using the DFS order. However, a specific technique is often employed to optimize space.

Standard approaches might allocate O(depth) memory for every node, which is costly. Instead, LCD allows us to store DP information for an entire long chain in a contiguous static array. By utiliizng pointers or offset indices, we can inherit the DP state of the long son in O(1) time. When processing a node, we "steal" the buffer used by its long son and simply prepend the current node's data.

Practical Applications

1. Finding the k-th Ancestor

While Binary Lifting solves this in O((n + q) log n), and an offline stack-based method works in O(n + q), LCD offers an interesting online approach with O(n log n + q) complexity.

After decomposition, we preprocess each chain. For every node in a chain, we store the nodes len steps above it (upward jump) and len steps below it (downward jump) within the chain.

**Query Logic:**1. First, use Binary Lifting to jump up approximately log_2(k) levels. 2. The remaining distance to the target is rem. 3. Since the length of the current chain is at least rem (guaranteed by the properties of LCD), the target is guaranteed to be within the pre-recorded array of the current chain.

2. Dominant Indices (Problem Analysis)

This problem can be solved using "DSU on Tree," but LCD provides a linear O(n) solution. The strategy resembles DSU on Tree:

1. Recursively process the long son.
2. Inherit the DP array (count of nodes at specific depths) from the long son directly via the pointer/buffer offset technique.
3. Merge contributions from light sons by brute force iteration.

Since each node contributes to the brute-force merge only when it is in a light subtree relative to its parent, the total complexity is linear. Heavy-Light Decomposition fails here because a light child might be deeper than the heavy child, preventing simple pointer inheritance without resizing.

3. Dynamic Programming on Trees (HOT-hotel Example)

This scenario demonstrates optimizing DP with depth dependencies using LCD and dynamic memory allocaiton.

Let f(u, i) be the number of nodes in the subtree of u at distance i from u. Let g(u, i) be the number of pairs of nodes in the subtree of u such that their distance is 2 * i (they are equidistant from u), essentially looking for a third node outside the subtree to complete a specific structure.

The transitions involve shifting indices (left or right) corresponding to depth changes. By allocating arrays based on the DFS order and the length of long chains, we optimize memory access.

int dp_dfn[MAXN], cursor;
int top_node[MAXN];
int max_len[MAXN]; // Length of the chain starting at top_node

// Global arrays for DP states to allow pointer shifting
int F[MAXN * 2], G[MAXN * 2]; 
int ptr_f[MAXN], ptr_g[MAXN]; // Pointers for the start of valid data

long long global_ans = 0;

void decompose_dp(int u, int chain_top) {
    top_node[u] = chain_top;
    dp_dfn[u] = ++cursor;
    // Setup pointers for the chain
    // We reserve space: [base, base + max_len * 2]
    ptr_f[chain_top] = cursor + max_len[chain_top]; 
    ptr_g[chain_top] = cursor;
    // ... (logic omitted for brevity) ...
}

void solve_dp(int u, int parent) {
    if (!long_child[u]) {
        // Base case: Leaf node
        F[ptr_f[top_node[u]]] = 1; // 1 node at distance 0
        return;
    }

    // Recurse
    for (int i = head[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (v != parent) solve_dp(v, u);
    }

    int chain_top = top_node[u];
    
    // Update answer using the child's G array (shifted)
    global_ans += G[ptr_g[chain_top] + 1];
    
    // Add current node to F (shifting array "down" virtually)
    ptr_f[chain_top]--;
    F[ptr_f[chain_top]] = 1; 
    
    // Shift G array "up" (virtual left shift)
    ptr_g[chain_top]++;

    // Merge light children
    for (int i = head[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (v == parent || v == long_child[u]) continue;
        
        int child_top = top_node[v];
        for (int j = 0; j <= max_len[v]; ++j) {
            // Combine states from light child into current chain
            global_ans += 1LL * F[ptr_f[chain_top] + j] * G[ptr_g[child_top] + j + 1];
            global_ans += 1LL * G[ptr_g[chain_top] + j] * (j ? F[ptr_f[child_top] + j - 1] : 0);
        }
        
        for (int j = 0; j <= max_len[v]; ++j) {
            G[ptr_g[chain_top] + j] += G[ptr_g[child_top] + j + 1];
        }
        
        for (int j = 1; j <= max_len[v]; ++j) {
            G[ptr_g[chain_top] + j] += 1LL * F[ptr_f[chain_top] + j] * F[ptr_f[child_top] + j - 1];
            F[ptr_f[chain_top] + j] += F[ptr_f[child_top] + j - 1];
        }
    }
}

4. Complex Queries (WC2010 Reconstruction Plan)

In problems requiring range maximum queries on the DP arrays (e.g., finding the maximum number of nodes at a specific distance), LCD can be combined with Segment Trees.

Since the DP information for a long chain is stored in a contiguous array interval corresponding to the DFS order, a Segment Tree can be built over this order. This allows efficient range maximum queries (RMQ) during the DP transitions or while answering complex path queries.