Tree-based dynamic programming relies on post-order traversal (processing children before parents). The standard recursive skeleton ensures proper state aggregation without cyclic revisits:

void traverse(int current_node, int parent_node) {
    // Process leaf/base case initialization if necessary
    
    for (auto& edge : adjacency_list[current_node]) {
        int next_node = edge.to;
        int edge_weight = edge.cost;
        
        if (next_node == parent_node) continue;
        
        traverse(next_node, current_node);
        
        // Combine results from child into current state
    }
}

The computational relationship hinges on deriving the optimal state of a parent node from the aggregated results of its descendants.

Determining Tree Diameter

Problem Specification

Given a weighted undirected tree with $N$ vertices and $N-1$ edges, calculate the maximum path weight between any two vertices. The graph contains no cycles and remains connected.

Input Format

First line: integer $N$ ($2 \leq N \leq 2 \times 10^5$). Next $N-1$ lines: integers $u, v, w$ representing an undirected edge with weight $w$ ($w \leq 10^9$).

Output Format

Single integer representing the diameter length.

Algorithmic Approach

For any node $u$, the longest path passing through $u$ consists of the two longest downward branches extending into its subtrees. We maintain a state max_downward_chain[u] tracking the single longest path starting at $u$ and descending. During traversal, we compare the sum of the top two child chains plus their connecting edge weights against a global maximum tracker.

Implementation

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

struct Link {
    int target;
    int weight;
};

const int MAX_N = 200005;
vector<Link> graph[MAX_N];
long long longest_descendant[MAX_N];
long long global_diameter = 0;

void compute_diameter(int u, int parent) {
    for (const auto& e : graph[u]) {
        int v = e.target;
        if (v == parent) continue;
        
        compute_diameter(v, u);
        
        // Update global answer considering paths crossing u
        global_diameter = max(global_diameter, longest_descendant[u] + longest_descendant[v] + e.weight);
        
        // Update current node's longest downward path
        longest_descendant[u] = max(longest_descendant[u], longest_descendant[v] + e.weight);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    if (!(cin >> n)) return 0;
    
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    
    compute_diameter(1, -1);
    cout << global_diameter << '\n';
    return 0;
}

Calculating Maximum Distance Per Node

Problem Specification

In a network topology modeled as a tree, determine the maximum distance from every node to any other node in the graph.

Input Format

First line: integer $N$ ($N \leq 10^4$). Next $N-1$ lines: integer $p_i, d_i$ indicating node $i$ connects to parent $p_i$ with distance $d_i$.

Output Format

$N$ lines, each containing the maximum distance from the corresponding node index.

Algorithmic Approach

A fundamental property states that the farthest node from any given vertex must be one of the two endpoints of the tree's diameter. By identifying these endpoints via breadth-first or depth-first search, we can compute exact distances from both endpoints to all other nodes. The result for each vertex is simply the maximum of these two distance arrays.

Implementation

#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 10005;
struct Connection {
    int dest;
    int dist;
};

vector<Connection> adj[MAX_N];
int dist_from_endpoint_a[MAX_N];
int dist_from_endpoint_b[MAX_N];
int farthest_node_idx;
int max_dist_found;

void find_farthest(const vector<Connection>* g, int u, int p) {
    for (const auto& edge : g[u]) {
        if (edge.dest == p) continue;
        dist_from_endpoint_a[edge.dest] = dist_from_endpoint_a[u] + edge.dist;
        find_farthest(g, edge.dest, u);
    }
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    for (int i = 2; i <= n; ++i) {
        int parent, distance;
        cin >> parent >> distance;
        adj[i].push_back({parent, distance});
        adj[parent].push_back({i, distance});
    }
    
    // Pass 1: Locate first diameter endpoint
    find_farthest(adj, 1, -1);
    max_dist_found = 0;
    for (int i = 1; i <= n; ++i) {
        if (dist_from_endpoint_a[i] > max_dist_found) {
            max_dist_found = dist_from_endpoint_a[i];
            farthest_node_idx = i;
        }
    }
    
    // Pass 2: Locate second endpoint & record distances from first
    memset(dist_from_endpoint_a, 0, sizeof(dist_from_endpoint_a));
    find_farthest(adj, farthest_node_idx, -1);
    
    max_dist_found = 0;
    for (int i = 1; i <= n; ++i) {
        if (dist_from_endpoint_a[i] > max_dist_found) {
            max_dist_found = dist_from_endpoint_a[i];
            farthest_node_idx = i;
        }
    }
    
    // Pass 3: Record distances from second endpoint
    memset(dist_from_endpoint_a, 0, sizeof(dist_from_endpoint_a));
    memcpy(dist_from_endpoint_b, dist_from_endpoint_a, sizeof(dist_from_endpoint_a));
    find_farthest(adj, farthest_node_idx, -1);
    
    // Compute final answers
    for (int i = 1; i <= n; ++i) {
        cout << max(dist_from_endpoint_a[i], dist_from_endpoint_b[i]) << '\n';
    }
    
    return 0;
}

Optimal Facility Placement via Rerooting

Problem Specification

Given a binary tree where nodes carry population weights and edges represent unit distances, place a single facility at a node to minimize the total weighted travel distance for all residents.

Input Format

First line: integer $n$ ($n \leq 100$). Next $n$ lines: $population, left_child_id, right_child_id$.

Output Format

Single integer representing the minimized total distance.

Algorithmic Approach

A naive $O(N^2)$ recalculation for each potantial facility location is inefficient. Instead, apply the rerooting technique. First, compute the total cost assuming the facility is at the root. Then, recursively propagate this cost to adjacent nodes. When shifting the root from parent $u$ to child $v$, nodes within $v$'s subtree become 1 step closer, while all other nodes become 1 step farther. The recurrence relation becomes: $$ \text{Cost}_v = \text{Cost}_u - 2 \times \text{Population}_v + \text{TotalPopulation} $$

Implementation

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAX_N = 105;
struct TreeNode {
    int population;
    int left_child = 0;
    int right_child = 0;
};

TreeNode nodes[MAX_N];
int subtree_pop[MAX_N];
long long initial_cost = 0;
int total_population = 0;

void calculate_subtree_pops(int u) {
    subtree_pop[u] = nodes[u].population;
    if (nodes[u].left_child) {
        calculate_subtree_pops(nodes[u].left_child);
        subtree_pop[u] += subtree_pop[nodes[u].left_child];
    }
    if (nodes[u].right_child) {
        calculate_subtree_pops(nodes[u].right_child);
        subtree_pop[u] += subtree_pop[nodes[u].right_child];
    }
}

void compute_root_cost(int u, int depth) {
    initial_cost += (long long)depth * nodes[u].population;
    if (nodes[u].left_child) compute_root_cost(nodes[u].left_child, depth + 1);
    if (nodes[u].right_child) compute_root_cost(nodes[u].right_child, depth + 1);
}

long long costs[MAX_N];

void propagate_costs(int u, int v) {
    costs[v] = costs[u] - 2LL * subtree_pop[v] + total_population;
    if (nodes[u].left_child == v) {
        if (nodes[v].left_child) propagate_costs(v, nodes[v].left_child);
        if (nodes[v].right_child) propagate_costs(v, nodes[v].right_child);
    } else {
        if (nodes[v].left_child) propagate_costs(v, nodes[v].left_child);
        if (nodes[v].right_child) propagate_costs(v, nodes[v].right_child);
    }
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    for (int i = 1; i <= n; ++i) {
        cin >> nodes[i].population >> nodes[i].left_child >> nodes[i].right_child;
        total_population += nodes[i].population;
    }
    
    calculate_subtree_pops(1);
    compute_root_cost(1, 0);
    
    costs[1] = initial_cost;
    if (nodes[1].left_child) propagate_costs(1, nodes[1].left_child);
    if (nodes[1].right_child) propagate_costs(1, nodes[1].right_child);
    
    long long min_total_distance = costs[1];
    for (int i = 2; i <= n; ++i) {
        min_total_distance = min(min_total_distance, costs[i]);
    }
    
    cout << min_total_distance << '\n';
    return 0;
}

Maximizing Minimum Path Length with Binary Search

Problem Specification

Construct exactly $m$ non-overlapping paths in a weighted tree such that the length of the shortest constructed path is maximized. Each edge belongs to at most one path.

Input Format

First line: integers $n, m$ ($2 \leq n \leq 5 \times 10^4$, $1 \leq m \leq n-1$). Next $n-1$ lines: $u, v, w$ describing weighted edges.

Output Format

Maximum possible value for the minimum path length among the $m$ constructed paths.

Algorithmic Approach

The objective functon exhibits monotonicity, enabling binary search over the answer space. For a candidate minimum length $K$, determine if at least $m$ valid paths can be formed. The decision subroutine employs a greedy strategy combined with tree DP. At each node, aggregate valid path segments extending from children. Pair the shortest compatible segments with longer ones to satisfy threshold $K$. Unpaired segments that exceed $K$ contribute to the path count, while the longest remainder propagates upward.

Implementation

#include <vector>
#include <set>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 50005;
struct Edge {
    int target;
    int weight;
};

vector<Edge> tree_adj[MAX_N];
int matched_paths = 0;
int target_threshold;
long long max_segment_returned[MAX_N];
int global_m;

void evaluate_subtrees(int u, int p) {
    multiset<int> active_segments;
    
    for (const auto& e : tree_adj[u]) {
        int v = e.target;
        if (v == p) continue;
        
        evaluate_subtrees(v, u);
        int segment_len = max_segment_returned[v] + e.weight;
        
        if (segment_len >= target_threshold) {
            matched_paths++;
        } else {
            active_segments.insert(segment_len);
        }
    }
    
    while (!active_segments.empty()) {
        auto it_small = active_segments.begin();
        active_segments.erase(it_small);
        int val_small = *it_small;
        
        auto it_large = active_segments.lower_bound(target_threshold - val_small);
        if (it_large != active_segments.end()) {
            matched_paths++;
            active_segments.erase(it_large);
        } else {
            max_segment_returned[u] = max(max_segment_returned[u], val_small);
        }
    }
}

bool can_form(int limit) {
    target_threshold = limit;
    matched_paths = 0;
    fill(max_segment_returned, max_segment_returned + MAX_N, 0);
    evaluate_subtrees(1, -1);
    return matched_paths >= global_m;
}

int main() {
    int n;
    if (!(cin >> n >> global_m)) return 0;
    
    long long sum_weights = 0;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        tree_adj[u].push_back({v, w});
        tree_adj[v].push_back({u, w});
        sum_weights += w;
    }
    
    int low = 1, high = sum_weights / global_m + 1;
    int best_answer = 0;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (can_form(mid)) {
            best_answer = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    cout << best_answer << '\n';
    return 0;
}