Skip to content

DP on Treesđź”—

Used when input is a tree (acyclic connected graph) and we need to calculate DP states at each node, often in a bottom-up (post-order) or top-down (rerooting) fashion.

Post-order DFS (Bottom Up Tree DP)đź”—

We process children first, then compute the parent’s result using children’s DP.

vector<int> adj[N];
int dp[N];

void dfs(int node, int parent) {
    for (int child : adj[node]) {
        if (child == parent) continue;
        dfs(child, node);
        dp[node] += dp[child];  // Combine child results
    }
    dp[node] += value[node];  // Include current node’s own value
}

Common Patternsđź”—

Subtree Sizeđź”—

int size[N];

void dfs(int u, int p) {
    size[u] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        size[u] += size[v];
    }
}

Longest Path (Diameter of Tree)đź”—

int diameter = 0;

int dfs(int u, int p) {
    int max1 = 0, max2 = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        int d = dfs(v, u);
        if (d > max1) {
            max2 = max1;
            max1 = d;
        } else if (d > max2) {
            max2 = d;
        }
    }
    diameter = max(diameter, max1 + max2);
    return max1 + 1;
}

Tree Rerooting (Top-Down Tree DP)đź”—

We compute dp[root], then update dp[child] by “rerooting” at each child using the parent’s value.

void dfs1(int u, int p) {
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs1(v, u);
        dp[u] += dp[v] + size[v];
    }
}

void dfs2(int u, int p) {
    for (int v : adj[u]) {
        if (v == p) continue;
        dp[v] = dp[u] - size[v] + (total_nodes - size[v]);
        dfs2(v, u);
    }
}

Problemsđź”—

Easy to Medium

Medium to Hard