Point and Edge Divide and Conquer

Point and edge divide and conquer are algorithmic techniques that extend the concept of sequence divide and conquer to tree structures. The core idea involves selecting a "center" (a node or an edge) to partition the tree into smaller, independent sub-problems. To ensure efficiency and balance, we specifically look for the "center of gravity" in point divide and conquer or perform "edge tri-degree transformation" in edge divide and conquer. The remaining logic closely mirrors the standard divide-and-conquer approach used on linear sequences.

Point Divide and Conquer

In sequence divide and conquer, we typically select a midpoint, process contributions crossing the midpoint, and then recursively solve the left and right subarrays. Similarly, in point divide and conquer, we locate the center of gravity (centroid) of the tree, calculate the statistics for paths passing through this centroid, and then recursively handle the resulting subtrees.

A basic template for this algorithm looks like this:

void solve_subtree(int current_node) {
    compute_paths(current_node); // Handle answers passing through the center
    visited[current_node] = true; // Mark boundary to prevent revisiting

    for (int edge = head[current_node]; edge; edge = next[edge]) {
        int neighbor = to[edge];
        if (visited[neighbor]) continue;

        min_size = INF;
        find_centroid(neighbor, current_node, component_size[neighbor]); // Find centroid
        solve_subtree(centroid); // Recursive step
    }
}

When computing the answer, we must ensure that we do not pair two nodes originating from the same child subtree of the centroid. This often transforms the problem into a dynamic one: insert nodes from one subtree, query against existing data, repeat for all subtrees, and then backtrack. Alternatively, we can record the source subtree for each node and process everything offline using sorting, although this applies to fewer scenarios.

void compute_paths(int root) {
    for (int edge = head[root]; edge; edge = next[edge]) {
        int child = to[edge];
        if (visited[child]) continue;

        buffer_count = 0;
        collect_nodes(child, root); // Gather nodes into buffer array

        for (int i = prev_idx; i <= buffer_count; ++i) {
            // Perform queries using current buffer
        }
        for (int i = prev_idx; i <= buffer_count; ++i) {
            // Insert/Update data structures
        }
    }
    // Backtrack: Clear or remove inserted data
}

Example Problems

1. P3806 Point Divide and Conquer Template
The task ivnolves checking if point pairs with a specific distance $k$ exist for multiple queries ($m \le 100$) on a tree ($n \le 10^4$). For the online approach, data structures like buckets or unordered_map are suitable. Since we only need to check existence (feasibility), offline sorting with pointers is also efficient, as it allows us to quickly exclude pairs from the same subtree.

2. P7565 Beaver's Meeting 2
This problem asks for the maximum number of "expected" points for meetings of various sizes. Effectively, for each $j$, we need to find the longest chain where the bottom nodes of the chain have at least $j$ descendants. Due to the properties of the centroid, we can ignore nodes already processed by previous recursion steps. The solution involves maintaining a bucket that tracks the maximum chain length for a given chain bottom size. Updates are handled during the DFS traversal, and a suffix sum is used to derive the answer.

3. P2305 Ticketing
This problem resembles CDQ divide and conquer on a tree. We process the parent side of the centroid first (left side), then handle the current constraints, and finally recurse into the other subtrees. By sorting nodes based on $depth_v - l_v$, we can maintain valid "modifications" using a pointer. Because modifications are inserted in a specific order, a monotonic stack can be used for insertion, and binary search for queries.

Edge Divide and Conquer

Edge divide and conquer operates similarly to point divide and conquer, but instead of selecting a node, we select an edge as the partition center. This means we only process paths that traverse this specific edge. The advantage is that we naturally only have two sides to manage, eliminating the complexity of excluding intra-subtree pairs found in point divide and conquer.

However, this approach is vulnerable to star graphs, which can degrade performance to $O(N^2)$. To mitigate this, we apply edge tri-degree transformation. A common method involves connecting all child nodes of a high-degree node via a chain of dummy nodes.

int dummy_node_count, last_chain_node[MAX_SIZE];

void transform_edge(int u, int v, int w) {
    // Ensure u is the parent side or the side with larger size
    if (subtree_size[u] < subtree_size[v]) std::swap(u, v);

    if (!last_chain_node[u]) {
        last_chain_node[u] = u;
        add_graph_edge(last_chain_node[u], v, w);
    } else {
        int dummy = ++dummy_node_count;
        add_graph_edge(last_chain_node[u], dummy, 0); // 0 weight for internal dummy edges
        last_chain_node[u] = dummy;
        add_graph_edge(dummy, v, w);
    }
}

Finding the dividing edge effectively corresponds to finding the centroid in the transformed structure. Once found, we "remove" the edge (e.g., by setting the target of the edge to 0) and recurse.

Example: P4565 Brute Force Hanging

This problem involves two trees, $T_1$ and $T_2$, and requires calculating a specific maximum value involving depths and LCAs. While point divide and conquer can establish the formula, excluding nodes from the same subtree becomes difficult when more than two subtrees are involved. Edge divide and conquer solves this by strictly separating the tree into two sides, allowing us to easily manage the exclusion logic using specific variables for each side.

Point Divide Tree

Standard divide and conquer algorithms are typiaclly offline and do not handle modifications well. To support dynamic updates and queries, we use the Point Divide Tree (or Centroid Tree). This structure pre-computes the divide and conquer centers and builds a new tree connecting them.

Construction involves recursively finding centroids and connecting the centroids of subtrees to the current centroid:

void build_divide_tree(int u) {
    visited[u] = true;
    for (int edge = head[u]; edge; edge = next[edge]) {
        int v = to[edge];
        if (visited[v]) continue;

        min_size = INF;
        find_centroid(v, u, component_size[v]); // Find centroid in subtree
        int child_cen = centroid;
        
        parent_in_divide_tree[child_cen] = u;
        divide_tree_adj[u].push_back(child_cen);
        
        // Pre-calculate initial info if necessary
        collect_initial_data(v, u);
        
        build_divide_tree(child_cen);
    }
}

The point divide tree has two key properties:

1. Its height is $O(\log N)$.
2. The LCA of two nodes $x$ and $y$ in the divide tree lies on the path between $x$ and $y$ in the original tree.

These properties allow us to answer path queries by simply traversing ancestors in the divide tree. Since a node's information is stored in all its divide tree ancestors (of which there are only $O(\log N)$), we can support both updates and queries efficiently.

Similar to the standard divide and conquer, we must exclude contributions from the same subtree. We typically maintain two sets of data structures, $f$ and $g$, for each node in the divide tree:

• $f_x$: Represents the contribution of all points in $x$'s divide tree subtree to $x$ itself.
• $g_x$: Represents the contribution of all points in $x$'s divide tree subtree to $x$'s parent.

This separation allows us to calculate contributions using inclusion-exclusion: sum $f$ values and subtract $g$ values.

void update_path(int node, int val) {
    int current = node;
    // Update f at the node itself
    update_structure(f[current], distance_to_self(current), val);

    while (parent_in_divide_tree[current]) {
        int p = parent_in_divide_tree[current];
        int dist = get_distance(current, p);
        // Update g at current (contribution to parent)
        update_structure(g[current], dist, val);
        // Update f at parent
        update_structure(f[p], dist, val);
        current = p;
    }
}

int query_path(int node, int limit) {
    int current = node;
    int ans = query_structure(f[current], limit);

    while (parent_in_divide_tree[current]) {
        int p = parent_in_divide_tree[current];
        int dist = get_distance(current, p);
        if (limit >= dist) {
            ans += query_structure(f[p], limit - dist);
            ans -= query_structure(g[current], limit - dist);
        }
        current = p;
    }
    return ans;
}

Example Problems

1. P6329 Shockwave
This problem involves querying the sum of point weights within a distance $p$ from a node $u$, with modifications. Using the divide tree, we map the distance constraint relative to the query node to distance constraints relative to the divide tree ancestors. We use Binary Indexed Trees (Fenwick Trees) for the $f$ and $g$ arrays to support point updates and range queries within the logarithmic depth constraints.

2. P4115 Qtree4
This problem asks for the longest diameter in a dynamic set of nodes. We can maintain the farthest distance from each centroid to the active nodes. Since updates involve adding and removing nodes, we use removable heaps (priority queues supporting lazy deletion) to maintain the maximum values in $f$ and $g$. The answer is the maximum sum of the top two values in $f$ for any centroid.