Tree Diameter Calcualtion

To compute the longest path in an undirected weighted tree, we use a depth-first search (DFS) approach that tracks the top two maximum distances from the current node to any leaf in its subtree. The sum of these two values gives a candidate for the tree's diameter, which we update globally.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_NODES = 10005, MAX_EDGES = MAX_NODES * 2;
int nodeCount, edgeList[MAX_EDGES], nextEdge[MAX_EDGES], weights[MAX_EDGES], head[MAX_NODES], edgeIdx;
int maxDiameter;

void insertEdge(int from, int to, int weight) {
    edgeList[edgeIdx] = to, weights[edgeIdx] = weight, nextEdge[edgeIdx] = head[from], head[from] = edgeIdx++;
}

int exploreSubtree(int current, int parent) {
    int firstMax = 0, secondMax = 0;
    for (int i = head[current]; ~i; i = nextEdge[i]) {
        int neighbor = edgeList[i];
        if (neighbor == parent) continue;
        int childMax = exploreSubtree(neighbor, current) + weights[i];
        if (childMax > firstMax) {
            secondMax = firstMax;
            firstMax = childMax;
        } else if (childMax > secondMax) {
            secondMax = childMax;
        }
    }
    maxDiameter = max(maxDiameter, firstMax + secondMax);
    return firstMax;
}

int main() {
    cin >> nodeCount;
    memset(head, -1, sizeof head);
    for (int i = 0; i < nodeCount - 1; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        insertEdge(a, b, c);
        insertEdge(b, a, c);
    }
    exploreSubtree(1, -1);
    cout << maxDiameter << endl;
    return 0;
}

Finding the Tree's Center Node

The tree center is the node that minimizes its maximum distance to all other nodes. We perform two DFS passes: one to compute the top two downward maximum distances and track which child contributes to the longest path, and another to calculate the upward maximum distance from each node via its parent. The minimum of the maximum upward and downward distances across all nodes gives the answer.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_NODES = 10005, MAX_EDGES = MAX_NODES * 2, INF = 1e9;
int nodeCount, edgeList[MAX_EDGES], nextEdge[MAX_EDGES], weights[MAX_EDGES], head[MAX_NODES], edgeIdx;
int down1[MAX_NODES], down2[MAX_NODES], upDist[MAX_NODES], longestChild[MAX_NODES];
bool isLeaf[MAX_NODES];

void insertEdge(int from, int to, int weight) {
    edgeList[edgeIdx] = to, weights[edgeIdx] = weight, nextEdge[edgeIdx] = head[from], head[from] = edgeIdx++;
}

int computeDownward(int current, int parent) {
    down1[current] = -INF, down2[current] = -INF;
    for (int i = head[current]; ~i; i = nextEdge[i]) {
        int neighbor = edgeList[i];
        if (neighbor == parent) continue;
        int childRes = computeDownward(neighbor, current) + weights[i];
        if (childRes > down1[current]) {
            down2[current] = down1[current];
            down1[current] = childRes;
            longestChild[current] = neighbor;
        } else if (childRes > down2[current]) {
            down2[current] = childRes;
        }
    }
    if (down1[current] == -INF) {
        down1[current] = down2[current] = 0;
        isLeaf[current] = true;
    }
    return down1[current];
}

void computeUpward(int current, int parent) {
    for (int i = head[current]; ~i; i = nextEdge[i]) {
        int neighbor = edgeList[i];
        if (neighbor == parent) continue;
        if (longestChild[current] == neighbor) {
            upDist[neighbor] = max(upDist[current], down2[current]) + weights[i];
        } else {
            upDist[neighbor] = max(upDist[current], down1[current]) + weights[i];
        }
        computeUpward(neighbor, current);
    }
}

int main() {
    cin >> nodeCount;
    memset(head, -1, sizeof head);
    for (int i = 0; i < nodeCount - 1; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        insertEdge(a, b, c);
        insertEdge(b, a, c);
    }
    computeDownward(1, -1);
    computeUpward(1, -1);
    int minMaxDist = down1[1];
    for (int i = 2; i <= nodeCount; ++i) {
        int candidate = isLeaf[i] ? upDist[i] : max(down1[i], upDist[i]);
        minMaxDist = min(minMaxDist, candidate);
    }
    cout << minMaxDist << endl;
    return 0;
}

Number Transformation Diameter

We first precompute the sum of proper divisors for every number up to n. For each number i (starting from 2), if its proper divisor sum s[i] is less than i, we add a directed edge from s[i] to i. This forms a forest of trees, and we compute the diameter of each tree to find the overall maximum.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_NUM = 50005;
int upperLimit;
int divisorSum[MAX_NUM], edgeList[MAX_NUM], nextEdge[MAX_NUM], head[MAX_NUM], edgeIdx;
bool hasParent[MAX_NUM];
int globalLongest;

void insertEdge(int from, int to) {
    edgeList[edgeIdx] = to, nextEdge[edgeIdx] = head[from], head[from] = edgeIdx++;
}

int dfsTree(int node) {
    int max1 = 0, max2 = 0;
    for (int i = head[node]; ~i; i = nextEdge[i]) {
        int child = edgeList[i];
        int childDepth = dfsTree(child) + 1;
        if (childDepth > max1) {
            max2 = max1;
            max1 = childDepth;
        } else if (childDepth > max2) {
            max2 = childDepth;
        }
    }
    globalLongest = max(globalLongest, max1 + max2);
    return max1;
}

int main() {
    cin >> upperLimit;
    memset(head, -1, sizeof head);
    for (int i = 1; i <= upperLimit; ++i) {
        for (int j = 2; i * j <= upperLimit; ++j) {
            divisorSum[i * j] += i;
        }
    }
    for (int i = 2; i <= upperLimit; ++i) {
        if (divisorSum[i] < i) {
            insertEdge(divisorSum[i], i);
            hasParent[i] = true;
        }
    }
    for (int i = 1; i <= upperLimit; ++i) {
        if (!hasParent[i]) dfsTree(i);
    }
    cout << globalLongest << endl;
    return 0;
}

Binary Apple Tree Pruning

This is a tree-based knapsack problem. We define dp[node][k] as the maximum apples obtainable by keeping k edges in the subtree rooted at node. We process each child, performing a reverse 0-1 knapsack update to combine the child's subtree options with the current node's.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_NODES = 105, MAX_EDGES = MAX_NODES * 2;
int nodeCount, keepEdges;
int edgeList[MAX_EDGES], nextEdge[MAX_EDGES], weights[MAX_EDGES], head[MAX_NODES], edgeIdx;
int dp[MAX_NODES][MAX_NODES];

void insertEdge(int from, int to, int weight) {
    edgeList[edgeIdx] = to, weights[edgeIdx] = weight, nextEdge[edgeIdx] = head[from], head[from] = edgeIdx++;
}

void solveSubtree(int u, int parent) {
    for (int i = head[u]; ~i; i = nextEdge[i]) {
        int v = edgeList[i];
        if (v == parent) continue;
        solveSubtree(v, u);
        for (int j = keepEdges; j >= 1; --j) {
            for (int k = 0; k < j; ++k) {
                dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + weights[i]);
            }
        }
    }
}

int main() {
    cin >> nodeCount >> keepEdges;
    memset(head, -1, sizeof head);
    for (int i = 0; i < nodeCount - 1; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        insertEdge(a, b, c);
        insertEdge(b, a, c);
    }
    solveSubtree(1, -1);
    cout << dp[1][keepEdges] << endl;
    return 0;
}

Strategic Game

This basic tree DP problem asks for the minimum number of soldiers to place on nodes such that every edge is adjacent to at least one soldier. We track two states per node: dp[node][0] (no soldier) requiring all children to have soldiers, and dp[node][1] (soldier) allowing children to choose either state optimally.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_NODES = 1505;
int nodeCount;
int edgeList[MAX_NODES], nextEdge[MAX_NODES], head[MAX_NODES], edgeIdx;
int dp[MAX_NODES][2];
bool hasParent[MAX_NODES];

void insertEdge(int from, int to) {
    edgeList[edgeIdx] = to, nextEdge[edgeIdx] = head[from], head[from] = edgeIdx++;
}

void dfs(int u) {
    dp[u][0] = 0;
    dp[u][1] = 1;
    for (int i = head[u]; ~i; i = nextEdge[i]) {
        int v = edgeList[i];
        dfs(v);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][0], dp[v][1]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> nodeCount) {
        memset(head, -1, sizeof head);
        memset(hasParent, false, sizeof hasParent);
        edgeIdx = 0;
        for (int i = 0; i < nodeCount; ++i) {
            int x, cnt;
            char c;
            cin >> x >> c >> c >> cnt >> c;
            for (int j = 0; j < cnt; ++j) {
                int y;
                cin >> y;
                insertEdge(x, y);
                hasParent[y] = true;
            }
        }
        int root = 0;
        while (hasParent[root]) root++;
        dfs(root);
        cout << min(dp[root][0], dp[root][1]) << endl;
    }
    return 0;
}

Palace Guards

This problem extends the strategic game by requiring all nodes (not edges) to be guarded, with each guard covering itself, its parenet, and its children. We track three states: dp[node][0] (guarded by a child), dp[node][1] (guarded by itself), and dp[node][2] (guarded by its parenet). For dp[node][0], we ensure at least one child is placed with a guard by adjusting the sum of minimal child costs.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_NODES = 1505, INF = 0x3f3f3f3f;
int nodeCount;
int edgeList[MAX_NODES], nextEdge[MAX_NODES], cost[MAX_NODES], head[MAX_NODES], edgeIdx;
int dp[MAX_NODES][3];
bool hasParent[MAX_NODES];

void insertEdge(int from, int to) {
    edgeList[edgeIdx] = to, nextEdge[edgeIdx] = head[from], head[from] = edgeIdx++;
}

void dfs(int u) {
    dp[u][0] = INF;
    dp[u][1] = cost[u];
    dp[u][2] = 0;
    int minSum = 0;
    for (int i = head[u]; ~i; i = nextEdge[i]) {
        int v = edgeList[i];
        dfs(v);
        dp[u][1] += min(min(dp[v][0], dp[v][1]), dp[v][2]);
        int childMin = min(dp[v][0], dp[v][1]);
        minSum += childMin;
        dp[u][2] += childMin;
    }
    for (int i = head[u]; ~i; i = nextEdge[i]) {
        int v = edgeList[i];
        dp[u][0] = min(dp[u][0], minSum - min(dp[v][0], dp[v][1]) + dp[v][1]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> nodeCount;
    memset(head, -1, sizeof head);
    for (int i = 0; i < nodeCount; ++i) {
        int x, val, cnt;
        cin >> x >> val >> cnt;
        cost[x] = val;
        for (int j = 0; j < cnt; ++j) {
            int y;
            cin >> y;
            insertEdge(x, y);
            hasParent[y] = true;
        }
    }
    int root = 1;
    while (hasParent[root]) root++;
    dfs(root);
    cout << min(dp[root][0], dp[root][1]) << endl;
    return 0;
}