Core Concepts

Tree Center Fundamentals

For any node in a tree, removing that node and its connected edges partitions the tree into several connected components. Let max_component[i] represent the size of the largest component after removing node i. The tree center is defined as the node that minimizes max_component[i].

A key property of tree centers is that the maximum component size of a tree center never exceeds half of the total nodes. This can be proven by contradiction.

To find the tree center, we compute size[x] (subtree size rooted at x) and for each node calculate max_component[x] = max(size[y] for y in children[x], total_nodes - size[x]). We include total_nodes - size[x] because nodes outside x's subtree form another component.

void find_subtree_size(int current, int parent) {
    int max_child = 0;
    subtree_size[current] = 1;
    
    for (Edge* edge = adjacency_list[current]; edge != nullptr; edge = edge->next) {
        int neighbor = edge->target;
        if (neighbor == parent) continue;
        
        find_subtree_size(neighbor, current);
        subtree_size[current] += subtree_size[neighbor];
        max_child = max(max_child, subtree_size[neighbor]);
    }
    
    max_child = max(max_child, total_nodes - subtree_size[current]);
    
    if (max_child < min_max_component) {
        centers.clear();
        min_max_component = max_child;
        centers.push_back(current);
    } else if (max_child == min_max_component) {
        centers.push_back(current);
    }
}

Algorithm Foundation

Centroid decomposition applies divide-and-conquer to solve tree path problems. In a rooted tree, paths can be categorized as either passing through the root or contained within subtrees. The algorithm first processes valid root-passing paths, then removes the root and recursively processes subtrees, converting non-root paths into root-passing paths within subtrees.

Selecting arbitrary roots could degrade complexity to O(n²) in worst-case scenarios (like chains). However, using the tree center as root ensures O(n log n) complexity. Since a center's maximum component size is at most n/2, each recursion level halves the problem size, resulting in logarithmic depth.

To find all valid root-passing paths, observe that such paths consist of left and right subtree chains. We process subtrees sequentially, using information from previously processed subtrees to compute current contributions.

Implementation Framework

The algorithm structure follows: find tree center, process subtree answers, recursive solve subtrees.

void locate_center(int current, int parent) {
    subtree_size[current] = 1;
    int max_component = 0;
    
    for (Edge* edge = adjacency_list[current]; edge != nullptr; edge = edge->next) {
        int neighbor = edge->target;
        int weight = edge->value;
        if (neighbor == parent || visited[neighbor]) continue;
        
        locate_center(neighbor, current);
        subtree_size[current] += subtree_size[neighbor];
        max_component = max(max_component, subtree_size[neighbor]);
    }
    
    max_component = max(max_component, current_tree_size - subtree_size[current]);
    
    if (max_component < min_component_size) {
        min_component_size = max_component;
        center_node = current;
    }
}

void compute_contributions(int current, int parent) {
    // Aggregate results from previously processed subtrees
}

void update_tracker(int current, int parent, int operation) {
    // Update tracking arrays after processing current subtree
}

void decompose_tree(int current) {
    visited[current] = true;
    
    for (Edge* edge = adjacency_list[current]; edge != nullptr; edge = edge->next) {
        int neighbor = edge->target;
        if (visited[neighbor]) continue;
        
        // Initialize values
        compute_contributions(neighbor, 0);
        update_tracker(neighbor, 0, 1);
    }
    
    for (Edge* edge = adjacency_list[current]; edge != nullptr; edge = edge->next) {
        int neighbor = edge->target;
        if (visited[neighbor]) continue;
        update_tracker(neighbor, 0, 0); // Reset tracking arrays
    }
    
    for (Edge* edge = adjacency_list[current]; edge != nullptr; edge = edge->next) {
        int neighbor = edge->target;
        if (visited[neighbor]) continue;
        current_tree_size = subtree_size[neighbor];
        center_node = 0;
        min_component_size = INT_MAX;
        locate_center(neighbor, 0);
        locate_center(center_node, 0); // Recompute sizes for accuracy
        decompose_tree(center_node);
    }
}

Practical Applications

Minimum Edge Path with Target Sum

Given a tree with weighted edges, find the path with exactly k total weight that uses the fewest edges.

We maintain a min_edges array where min_edges[d] stores the minimum edges needed to achieve distance d from the current root. During processing, we check if a path with length k - current_distance exists and update the answer accordingly.

void process_subtree(int current, int parent) {
    if (current_distance > target_sum) return;
    
    min_answer = min(min_answer, current_depth + min_edges[target_sum - current_distance]);
    
    for (Edge* edge = adjacency_list[current]; edge != nullptr; edge = edge->next) {
        int neighbor = edge->target;
        int weight = edge->value;
        if (neighbor == parent || visited[neighbor]) continue;
        
        current_distance += weight;
        current_depth += 1;
        process_subtree(neighbor, current);
    }
}

void update_distance_tracker(int current, int parent, int operation) {
    if (current_distance > target_sum) return;
    
    if (operation) {
        min_edges[current_distance] = min(min_edges[current_distance], current_depth);
    } else {
        min_edges[current_distance] = node_count;
    }
    
    for (Edge* edge = adjacency_list[current]; edge != nullptr; edge = edge->next) {
        int neighbor = edge->target;
        if (neighbor == parent || visited[neighbor]) continue;
        update_distance_tracker(neighbor, current, operation);
    }
}

Balanced Path Counting

Count paths where edge weights alternate between positive and negative values, and the path can be split at any point into two segments with equal sum.

We assign +1 to positive edges and -1 to negative edges. A path is balanced if its total sum is zero and can be split at some point where prefix sum equals suffix sum. We track distance occurrences with separate counters for paths with and without valid split points.

void traverse_subtree(int current, int parent) {
    max_depth = max(max_depth, abs(current_offset - base_offset));
    
    if (split_marker[current_offset]) {
        local_counter[current_offset][1]++;
    } else {
        local_counter[current_offset][0]++;
    }
    
    split_marker[current_offset]++;
    
    for (Edge* edge = adjacency_list[current]; edge != nullptr; edge = edge->next) {
        int neighbor = edge->target;
        int weight = edge->value;
        if (neighbor == parent || visited[neighbor]) continue;
        
        current_offset += weight;
        traverse_subtree(neighbor, current);
    }
    
    split_marker[current_offset]--;
}

Modular Path Counting

Count paths where the sum of edge weights is divisible by 3.

We maintain counters for distances modulo 3. The solution combines paths from different subtrees where the sum of their modular distances equals 0 mod 3.

void traverse_modular(int current, int parent) {
    modular_count[current_distance % 3]++;
    
    for (Edge* edge = adjacency_list[current]; edge != nullptr; edge = edge->next) {
        int neighbor = edge->target;
        int weight = edge->value;
        if (neighbor == parent || visited[neighbor]) continue;
        
        current_distance += weight;
        traverse_modular(neighbor, current);
    }
}

Maximum Product Path

Find the path that maximizes the product of minimum edge weight and total path weight.

We use a Fenwick tree to maintain maximum path weights for given minimum weights. For each path, we query the maximum path weight among all previously processed paths with minimum weight at least the current path's minimum.

void update_fenwick(int position, long long value) {
    while (position > 0) {
        fenwick[position] = max(fenwick[position], value);
        position -= position & -position;
    }
}

long long query_fenwick(int position) {
    long long result = 0;
    while (position <= max_value) {
        result = max(result, fenwick[position]);
        position += position & -position;
    }
    return result;
}

void process_paths(int current, int parent, long long current_min) {
    for (Edge* edge = adjacency_list[current]; edge != nullptr; edge = edge->next) {
        int neighbor = edge->target;
        int weight = edge->value;
        if (neighbor == parent || visited[neighbor]) continue;
        
        path_sum += weight;
        long long new_min = min(current_min, (long long)weight);
        
        max_answer = max(max_answer, new_min * (query_fenwick(new_min) + path_sum));
        process_paths(neighbor, current, new_min);
    }
}