Core Concept

Point divide and conquer is an offline algorithmic framework based on the divide and conquer paradigm, designed to solve problems involving paths on trees. The fundamental idea involves partitioning all tree paths into two categories: those that pass through a chosen root node, and those that do not. Paths passing through the root can be decomposed into two chains originating from the root. By efficiently combining these chains using auxiliary data structures, contributions to the solution can be calculated. The root is then marked as processed, dividing the tree into disjoint subtrees rooted at its children. The algorithm recurses into each subtree, selecting new roots until all nodes are processed.

Complexity Analysis

The choice of the root is critical for efficiency. Selecting the centroid of the current tree minimizes the complexity. A centroid is a node whose removal leaves no connected copmonent with more than half the tree's nodes. If the current tree has $n$ nodes, partitioning via the centroid ensures each resulting subtree has at most $n/2$ nodes. This guarantees a recursion depth of $O(\log n)$. Each level of recursion involves processing all nodes, typically in $O(n \log n)$ time when combined with data structures. Thus, the overall complexity is $O(n \log^2 n)$ or $O(n \log n)$, superior to naive $O(n^2)$ appproaches.

Generic Implementation Template

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 10;
const int MAX_EDGES = 2 * MAX_N;

struct Edge { int next, dest, weight; };
Edge edges[MAX_EDGES];
int adj_head[MAX_N], edge_count;
bool visited[MAX_N];
int subtree_size[MAX_N], max_component_size[MAX_N];
int centroid, total_nodes, result;

void add_edge(int src, int dst, int wt) {
    edges[++edge_count] = {adj_head[src], dst, wt};
    adj_head[src] = edge_count;
}

void compute_subtree_sizes(int node, int parent) {
    subtree_size[node] = 1;
    for (int i = adj_head[node]; i; i = edges[i].next) {
        int neighbor = edges[i].dest;
        if (neighbor == parent || visited[neighbor]) continue;
        compute_subtree_sizes(neighbor, node);
        subtree_size[node] += subtree_size[neighbor];
    }
}

void find_centroid(int node, int parent) {
    subtree_size[node] = 1;
    max_component_size[node] = 0;
    for (int i = adj_head[node]; i; i = edges[i].next) {
        int neighbor = edges[i].dest;
        if (neighbor == parent || visited[neighbor]) continue;
        find_centroid(neighbor, node);
        subtree_size[node] += subtree_size[neighbor];
        max_component_size[node] = max(max_component_size[node], subtree_size[neighbor]);
    }
    max_component_size[node] = max(max_component_size[node], total_nodes - subtree_size[node]);
    if (!centroid || max_component_size[node] < max_component_size[centroid])
        centroid = node;
}

void process_paths_through_centroid(int centroid) {
    visited[centroid] = true;
    // Logic to calculate contributions of paths passing through centroid
    // ...
}

void decompose(int node) {
    compute_subtree_sizes(node, 0);
    total_nodes = subtree_size[node];
    centroid = 0;
    find_centroid(node, 0);
    process_paths_through_centroid(centroid);
    for (int i = adj_head[centroid]; i; i = edges[i].next) {
        int neighbor = edges[i].dest;
        if (visited[neighbor]) continue;
        decompose(neighbor);
    }
}

int main() {
    int num_nodes;
    cin >> num_nodes;
    // Input reading and edge addition
    // ...
    decompose(1);
    cout << result << endl;
    return 0;
}

Example Applications

Minimum Edge Count Path with Sum K (IOI2011 Race)

Given a tree with weighted edges, find a simple path where the sum of edge weights equals $k$ and the number of edges is minimized. A bucket array tracks the minimum edge count for each possible sum up to $k$.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5 + 10;
const int MAX_K = 1e6 + 10;

struct Edge { int next, dest, weight; };
Edge graph[MAX_EDGES];
int adj_list[MAX_N], edge_idx;
bool processed[MAX_N];
int comp_size[MAX_N], max_comp_size[MAX_N];
int centroid_node, total_nodes, answer;
int min_edges_for_sum[MAX_K];

void add_connection(int u, int v, int w) {
    graph[++edge_idx] = {adj_list[u], v, w};
    adj_list[u] = edge_idx;
}

void calc_subtree_sizes(int u, int parent) {
    comp_size[u] = 1;
    for (int i = adj_list[u]; i; i = graph[i].next) {
        int v = graph[i].dest;
        if (v == parent || processed[v]) continue;
        calc_subtree_sizes(v, u);
        comp_size[u] += comp_size[v];
    }
}

void find_centroid(int u, int parent) {
    comp_size[u] = 1; max_comp_size[u] = 0;
    for (int i = adj_list[u]; i; i = graph[i].next) {
        int v = graph[i].dest;
        if (v == parent || processed[v]) continue;
        find_centroid(v, u);
        comp_size[u] += comp_size[v];
        max_comp_size[u] = max(max_comp_size[u], comp_size[v]);
    }
    max_comp_size[u] = max(max_comp_size[u], total_nodes - comp_size[u]);
    if (!centroid_node || max_comp_size[u] < max_comp_size[centroid_node])
        centroid_node = u;
}

void accumulate_paths(int u, int parent, int path_weight, int edge_count, int op) {
    if (path_weight > MAX_K) return;
    if (op == 0) {
        if (min_edges_for_sum[MAX_K - path_weight])
            answer = min(answer, edge_count + min_edges_for_sum[MAX_K - path_weight]);
    } else if (op == 1) {
        min_edges_for_sum[path_weight] = min(min_edges_for_sum[path_weight], edge_count);
    } else {
        min_edges_for_sum[path_weight] = MAX_N;
    }
    for (int i = adj_list[u]; i; i = graph[i].next) {
        int v = graph[i].dest;
        if (v == parent || processed[v]) continue;
        accumulate_paths(v, u, path_weight + graph[i].weight, edge_count + 1, op);
    }
}

void process_centroid(int center) {
    processed[center] = true;
    min_edges_for_sum[0] = 0;
    for (int i = adj_list[center]; i; i = graph[i].next) {
        int neighbor = graph[i].dest;
        if (processed[neighbor]) continue;
        accumulate_paths(neighbor, center, graph[i].weight, 1, 0);
        accumulate_paths(neighbor, center, graph[i].weight, 1, 1);
    }
    for (int i = adj_list[center]; i; i = graph[i].next) {
        int neighbor = graph[i].dest;
        if (processed[neighbor]) continue;
        accumulate_paths(neighbor, center, graph[i].weight, 1, 2);
    }
    for (int i = adj_list[center]; i; i = graph[i].next) {
        int neighbor = graph[i].dest;
        if (processed[neighbor]) continue;
        calc_subtree_sizes(neighbor, 0);
        total_nodes = comp_size[neighbor];
        centroid_node = 0;
        find_centroid(neighbor, 0);
        process_centroid(centroid_node);
    }
}

int main() {
    int num_nodes, k_val;
    cin >> num_nodes >> k_val;
    // Input reading
    // ...
    for (int i = 1; i <= k_val; i++) min_edges_for_sum[i] = MAX_N;
    total_nodes = num_nodes;
    centroid_node = 0;
    max_comp_size[0] = MAX_N;
    calc_subtree_sizes(1, 0);
    find_centroid(1, 0);
    answer = MAX_N;
    process_centroid(centroid_node);
    cout << (answer < MAX_N ? answer : -1) << endl;
    return 0;
}

Path with Balanced Binary Weights (Herder's Path)

Transform edge weights 0 and 1 to -1 and 1. Find paths where the sum is zero. Use two buckets to track paths with and without a midpoint (rest stop) where the sum is also zero.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 10;
const int OFFSET = MAX_N;

struct Edge { int next, dest, weight; };
Edge tree_edges[MAX_EDGES];
int tree_adj[MAX_N], edge_counter;
bool done[MAX_N];
int sz[MAX_N], max_sz[MAX_N];
int cent, total_n, sol;
int dist[MAX_N], max_dist;
int curr_bucket[2*MAX_N][2], prev_bucket[2*MAX_N][2];
int cnt[2*MAX_N];

void add_edge(int u, int v, int w) {
    tree_edges[++edge_counter] = {tree_adj[u], v, w};
    tree_adj[u] = edge_counter;
}

void get_subtree_sizes(int u, int p) {
    sz[u] = 1;
    for (int i = tree_adj[u]; i; i = tree_edges[i].next) {
        int v = tree_edges[i].dest;
        if (v == p || done[v]) continue;
        get_subtree_sizes(v, u);
        sz[u] += sz[v];
    }
}

void find_centroid(int u, int p) {
    sz[u] = 1; max_sz[u] = 0;
    for (int i = tree_adj[u]; i; i = tree_edges[i].next) {
        int v = tree_edges[i].dest;
        if (v == p || done[v]) continue;
        find_centroid(v, u);
        sz[u] += sz[v];
        max_sz[u] = max(max_sz[u], sz[v]);
    }
    max_sz[u] = max(max_sz[u], total_n - sz[u]);
    if (!cent || max_sz[u] < max_sz[cent]) cent = u;
}

void traverse_subtree(int u, int p, int cur_dist) {
    max_dist = max(max_dist, abs(cur_dist));
    if (cnt[cur_dist + OFFSET]) curr_bucket[cur_dist + OFFSET][1]++;
    else curr_bucket[cur_dist + OFFSET][0]++;
    cnt[cur_dist + OFFSET]++;
    for (int i = tree_adj[u]; i; i = tree_edges[i].next) {
        int v = tree_edges[i].dest;
        if (v == p || done[v]) continue;
        traverse_subtree(v, u, cur_dist + tree_edges[i].weight);
    }
    cnt[cur_dist + OFFSET]--;
}

void process_current_subtree(int u, int p, int cur_dist, int op) {
    if (op == 0) {
        for (int d = -max_dist; d <= max_dist; d++) {
            int idx = d + OFFSET;
            sol += (long long)curr_bucket[idx][0] * prev_bucket[-d + OFFSET][1];
            sol += (long long)curr_bucket[idx][1] * prev_bucket[-d + OFFSET][0];
            sol += (long long)curr_bucket[idx][1] * prev_bucket[-d + OFFSET][1];
        }
    } else if (op == 1) {
        for (int d = -max_dist; d <= max_dist; d++) {
            int idx = d + OFFSET;
            prev_bucket[idx][0] += curr_bucket[idx][0];
            prev_bucket[idx][1] += curr_bucket[idx][1];
            curr_bucket[idx][0] = curr_bucket[idx][1] = 0;
        }
    } else {
        for (int d = -max_dist; d <= max_dist; d++)
            cnt[d + OFFSET] = 0;
    }
}

void process_centroid_path(int center) {
    done[center] = true;
    prev_bucket[OFFSET][0] = 1;
    dist[center] = 0;
    max_dist = 0;
    for (int i = tree_adj[center]; i; i = tree_edges[i].next) {
        int v = tree_edges[i].dest;
        if (done[v]) continue;
        dist[v] = tree_edges[i].weight;
        traverse_subtree(v, center, dist[v]);
        process_current_subtree(v, center, dist[v], 0);
        process_current_subtree(v, center, dist[v], 1);
        traverse_subtree(v, center, dist[v]);
        process_current_subtree(v, center, dist[v], 2);
    }
    for (int i = tree_adj[center]; i; i = tree_edges[i].next) {
        int v = tree_edges[i].dest;
        if (done[v]) continue;
        get_subtree_sizes(v, 0);
        total_n = sz[v];
        cent = 0;
        find_centroid(v, 0);
        process_centroid_path(cent);
    }
}

int main() {
    int n;
    cin >> n;
    // Input reading, converting 0 to -1
    // ...
    total_n = n;
    cent = 0;
    max_sz[0] = MAX_N;
    get_subtree_sizes(1, 0);
    find_centroid(1, 0);
    process_centroid_path(cent);
    cout << sol << endl;
    return 0;
}