Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 63 ยท Graphs for Contests

Trees, Diameters and LCA

Solve contest tree problems in Python: iterative DFS, tree diameter, rerooting, binary lifting LCA and Euler tour subtree queries, all stress-tested.

A tree is a connected graph with no cycles: n vertices and exactly n - 1 edges, with one path between any two vertices. Trees appear in contests constantly, because many questions about them have clean O(n) or O(n log n) answers. Typical questions are "how far apart are the two farthest vertices?", "what is the lowest common ancestor of u and v?", and "what is the sum over a whole subtree?".

This lesson gives you a small toolbox: an iterative traversal, the diameter, rerooting, binary lifting for LCA, and the Euler tour. For the theory, see Tree Problems, Tree DP and Binary Lifting and LCA.

A traversal that never recurses

Python's recursion limit is about 1000 by default, and a tree can be a path of 10^5 vertices. Raising the limit is risky because deep recursion can crash the interpreter. In contests, prefer an iterative traversal that computes a parent array and a visiting order in one pass.

If you process the vertices in reverse order of that list, every child is handled before its parent. That gives you bottom-up dynamic programming (subtree sizes, subtree sums) without recursion. Processing the list in order gives top-down work (depths).

flowchart LR
    A["Adjacency list"] --> B["Iterative DFS from the root"]
    B --> C["order list and parent array"]
    C --> D["Reverse order: children before parents (bottom-up)"]
    C --> E["Forward order: parents before children (top-down)"]

One traversal gives you both directions of dynamic programming.

Diameter and rerooting

The diameter of a tree is the length of its longest path. A beautiful fact for trees (with non-negative edge weights): start at any vertex, find the farthest vertex a, then find the farthest vertex b from a. The path a to b is a diameter. Two BFS runs, O(n).

Rerooting answers questions of the form "what is X if vertex r is the root?" for all r at once. The classic example: for every vertex, the sum of distances to all other vertices. Computing it separately for every root costs O(n^2). Instead:

  1. Root the tree at 0. Compute size[v] (subtree sizes) and down[v], the sum of distances from v to the vertices in its own subtree. Process in reverse order: down[v] = sum(down[c] + size[c]) over children c.
  2. Compute ans[0] = down[0]. For a child c of v, moving the root from v to c brings the size[c] vertices in c's subtree one step closer and pushes the other n - size[c] vertices one step farther: ans[c] = ans[v] - size[c] + (n - size[c]).
Python Diameter by double BFS and rerooting distance sums

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A note about weights: the double-BFS trick extends to weighted trees with non-negative weights if you replace BFS by a distance computation along the tree (the same traversal, adding weights). It fails when edges can be negative.

Tree DP: the standard shapes

Tree DP means computing, for every vertex v, an answer about the subtree below v from the answers of its children. The traversal order from the first section does the work: process the vertices in reverse order, so each vertex is finished before its parent reads it. Almost every tree DP is one of three shapes.

  1. Aggregate over the subtree. Subtree size, height, number of leaves, sum of values. The recurrence is size[v] = 1 + sum(size[c]). Height is 1 + max(height[c]).
  2. Choose or skip a vertex. For "maximum weight set of vertices with no two adjacent" (a maximum independent set on a tree) keep two numbers per vertex: take[v], the best value in the subtree if v is chosen, and skip[v], the best value if it is not. Then take[v] = w[v] + sum(skip[c]) (children must be skipped) and skip[v] = sum(max(take[c], skip[c])). The answer is max(take[root], skip[root]).
  3. Best path through a vertex. For the maximum-sum path anywhere in the tree (vertex weights, possibly negative), keep down[v]: the best path that starts at v and goes down. A path that turns at v joins the two best downward paths of two different children. So down[v] = w[v] + max(0, best child down), and the candidate answer at v is w[v] + (best positive child down) + (second best positive child down). Negative branches are simply left out. The same two-best-children idea computes the diameter with edge weights.

The DP can go the other way, from the root down to the leaves, when a vertex's answer depends on its ancestors (for example, depth or "the best value among all ancestors"). When the answer for a vertex needs both what is below and what is above, you combine both passes: that is the rerooting technique from the section before.

Complexity is O(n) for each shape: every vertex combines its children once. Memory is a few arrays of length n.

Python Tree DP: sizes, independent set and best path

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Binary lifting and LCA

The lowest common ancestor (LCA) of u and v is the deepest vertex that is an ancestor of both. With the LCA you get path distances too: dist(u, v) = depth[u] + depth[v] - 2 * depth[lca].

Binary lifting stores up[k][v], the ancestor of v that is 2^k steps above it (or a sentinel if none). Build it from up[k][v] = up[k-1][ up[k-1][v] ]. To find the LCA:

  1. Lift the deeper vertex until both are at the same depth, jumping by powers of two read off the difference's binary digits.
  2. If they are now equal, that is the answer.
  3. Otherwise, from the highest k to the lowest, jump both vertices when their 2^k-th ancestors differ. After the loop, the parent of either vertex is the LCA.

Preprocessing is O(n log n) memory and time, each query O(log n).

Python LCA by binary lifting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In a contest with up to about 10^5 vertices and 10^5 queries, this runs comfortably in Python if you build up with list comprehensions as shown, instead of nested loops with attribute lookups.

Path aggregates with binary lifting

The same table that finds the LCA can answer "what is the maximum edge weight on the path from u to v?" in O(log n). Store a second table mx[k][v]: the maximum edge weight over the 2^k edges above v. It is built exactly like up: mx[k][v] = max(mx[k-1][v], mx[k-1][up[k-1][v]]). While you lift u and v towards the LCA, fold the maximum of every jump you take into a running answer. Any operation that is associative and does not need an inverse works the same way: minimum, maximum, sum, gcd, XOR. (For sums on a tree with updates, an Euler tour plus a Fenwick tree is the better tool.)

Python Maximum edge weight on a tree path

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Euler tour: subtrees as ranges

A DFS assigns each vertex an entry time tin[v] and an exit time tout[v]. Write the vertices in the order they were entered. Then the subtree of v is exactly the contiguous block tin[v] .. tout[v] - 1 of that list. This turns every subtree question into a range question, and you already know range tools: prefix sums for static data and Fenwick trees when values change.

The same times give an O(1) ancestor test: u is an ancestor of v exactly when tin[u] <= tin[v] < tout[u].

An iterative DFS needs a little care to record exit times. Push each vertex twice: once to enter it, and once (marked) to leave it.

Python Euler tour: subtree sums and ancestor tests

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Euler tours also give LCA in a different way (the minimum depth between two occurrences, found with a sparse table), and they are the first step of heavy-light decomposition and of "move a subtree" problems.

Putting it together

When you see a tree problem, run through this list:

  • Count and shape: is n up to 10^5 and the tree possibly a path? Then iterative traversal only.
  • "All roots at once" suggests rerooting.
  • "Distance between two vertices" suggests LCA plus depths.
  • "Subtree of v" suggests an Euler tour and a range structure.
  • "Farthest" suggests diameter endpoints: the farthest vertex from any vertex is always a diameter endpoint.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does processing the DFS order list in reverse give bottom-up dynamic programming?

    A vertex is added to the order when it is first reached, which is after its parent was. Reversing puts children first.
  2. 2. In rerooting, moving the root from v to its child c changes the distance sum by:

    The size[c] vertices inside c's subtree get one step closer, and the other n - size[c] vertices get one step farther.
  3. 3. After lifting both vertices to the same depth in binary lifting, what do you do if they are different?

    The loop stops just below the LCA, so the common parent of the two vertices is the answer.
  4. 4. In an Euler tour, which condition says u is an ancestor of v?

    Descendants are entered while u is still open, so their entry times fall in the half-open interval [tin[u], tout[u]).

Summary

  • Traverse trees iteratively; the visiting order gives bottom-up (reversed) and top-down (forward) passes.
  • The diameter comes from two BFS runs: farthest from anywhere, then farthest from that vertex.
  • Rerooting computes an answer for every root in O(n) by adjusting the parent's answer.
  • Binary lifting stores 2^k-th ancestors and answers LCA queries in O(log n); distance is depth[u] + depth[v] - 2 * depth[lca].
  • An Euler tour turns subtrees into contiguous ranges and gives an O(1) ancestor test.

Next: DP Problem Patterns