DP on a tree (Tree DP) - Course 4

Module 1: Trie

Trie

Module 2: Sparse Table

Sparse table

Module 3: Segment Tree

Segment tree
Maximum subarray sum on a given segment

Module 4: Segment Tree Lazy propagation

Segment Tree with Lazy Propagation

Module 5: More on trees

Euler order of visiting vertices
DP on a tree (Tree DP)

Module 6: Binary jumping

Binary Lifting (Jumps)
Lowest common ancestor

Module 7: Cyclic Games

Games on Cyclic Graphs

Module 8: Divide & Conquer

Divide and conquer

Module 9: SQRT Techniques

SQRT Decomposition
SQRT heuristics
Mo’s Algorithm

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Course 4/Module 5: More on trees/DP on a tree (Tree DP)

DP on a tree (Tree DP)

DP on a tree is a class of problems where the values at a vertex are computed based on the values of its children in the DFS tree.

Tree diameter

Diameter — the length of the maximum simple path between two vertices of a tree.

Classic DP idea:

For each vertex $x$ we compute:

$down[x]$ — the maximum depth of a path downward (to any descendant)

Then a path passing through $x$ :

$best[x] = \text{the two greatest depths among the children of } x + 2$

x

+

2

The global diameter is the maximum over all $best[x]$ .

The longest path through each vertex

For each vertex $x$ we need to find the length of the maximum path passing through it.

A path through a vertex can go:

down into one subtree
down into two different subtrees
up to ancestors

Therefore rerooting DP is done:

Compute downward: $down[x]$
Compute upward: $up[x]$ — the best path through the parent
Answer for the vertex:

$ans[x] = \max(\text{the two best depths around } x)$

Maximum matching in a tree

A matching is a set of edges with no common vertices.

Tree DP:

For vertex $x$ we compute:

$dp0[x]$ — the maximum in the subtree of $x$ if $x$ is not matched with the parent
$dp1[x]$ — the maximum if $x$ is matched with one of the children

Transitions:

$dp0[x]$ — the sum of maxima over the children
$dp1[x]$ — choose a child $y$ and match $(x,y)$

Thus:

$dp1[x] = \max_y \left( 1 + dp0[y] + \sum_{z \ne y} \max(dp0[z], dp1[z]) \right)$

Answer at the root:

$\max(dp0[root], dp1[root])$

This is the classic maximum matching in tree problem in $O(n)$ .

Also note that there exists a greedy solution where at each moment a leaf is taken and matched with an ancestor as long as possible. This can be implemented with a single DFS pass.

An interesting property of the diameter

Part 1

Choose any vertex $x$ .

Find the vertex $y$ farthest from it
Find the vertex $z$ farthest from $y$

Then the path $(y,z)$ is the diameter of the tree.

Part 2

Let there be a subset of vertices $S$ of the tree. Vertices are added one by one.

Claim:

There exist two vertices $a, b \in S$ such that for any vertex $v \in S$ :

$dist(a,b) = \max_{u,w \in S} dist(u,w)$

That is, the diameter of a set is always determined by a pair of vertices.

When adding a new vertex $v$ it is enough to check:

$dist(v,a),\quad dist(v,b)$

And update the pair $(a,b)$ if necessary.

This property is used in problems:

dynamic diameter of a set of vertices
online addition of vertices
problems on distances in a tree

void dfs(int x, int p) {
    for (int y: v[x]) {
        if (y == p) {
            continue;
        }
        dfs(y, x);
        down[x] = max(down[x], down[y] + 1);
    }
}

void dfs2(int x, int p) {
    vector<pair<int, int>> g;
    /*
        We can change this logic to linear by
        keeping two furthest only
    */
    for (int y: v[x]) {
        if (y == p) {
            continue;
        }
        g.push_back({down[y] + 1, y}); // distance to x
    }
    g.push_back({0, -1});
    sort(g.rbegin(), g.rend());
    for (int y: v[x]) {
        if (y == p) {
            continue;
        }
        up[y] = up[x] + 1;
        if (g[0].second == y) {
            up[y] = max(up[y], g[1].first + 1);
        } else {
            up[y] = max(up[y], g[0].first + 1);
        }
        dfs2(y, x);
    }
}