Graph (III)

Graph (III)
Ip Tsz Oi {ITO}
2024-04-06
 Graph (III) 2

Table of Contents

Overview & Revision

Rooted Tree

Binary Tree

Tree traversal

Tree diameter

Lowest common ancestor (LCA)

DAG and Topological Sort

Practice Problems
 Graph (III) 3

Overview & Revision

 Graph (III) 4

Prerequisite
● Graph (I)
○ basic concepts, graph representation, grid graph,
○ depth first search, flood fill, breadth first search
● Graph (II)
○ shortest path algorithms for weighted graphs,
○ minimum spanning tree
● Data Structures (III)
○ sparse table, segment tree,
○ lazy propagation, 1-d/2-d binary indexed tree
● Dynamic Programming (I)
○ Knapsack Problems
 Graph (III) 5

Overview
Tree:
● Definition and properties
Algorithms on tree:
● Pre-order, in-order and post-order
● Tree diameter
● Lowest common ancestor
● (DAG and topological sort)
 Graph (III) 6

Revision: tree
● A tree is a connected graph with no cycles.
● Vertices of a tree are also called nodes.
● A tree can be either weighted or unweighted, and
either rooted or unrooted.

Not a tree →
∵ has cycles
(e.g. {1, 6, 8})

← Tree
 Graph (III) 7

Revision: tree
● There are various equivalent definitions of a tree:
○ A connected graph with V vertices and V - 1 edges.
○ A connected graph with no cycles.
○ Between any two vertices on the graph, there is only one simple
(also the shortest) path between them.
● These properties make problems easier to solve.
 Graph (III) 8

Rooted Tree
 Graph (III) 9

Rooted tree
1
● Sometimes one of the nodes of the tree
will be viewed as the root of the tree
● Then the tree becomes directed 2 3

● (Note: if there is no root, we sometimes

choose any node as the root) 4 5 6

7 8

9 10
 Graph (III) 10

Rooted tree: terms

1

Parent 2 3

Sibling 4 5 6

As seen
from here
7 8

Children
9 10
 Graph (III) 11

Rooted tree: terms

1

Ancestors

2 3

4 5 6

As seen
from here
7 8

Descendants

9 10
 Graph (III) 12

Rooted tree: terms

1

2 3

4 5 6

As seen
from here
Subtrees 7 8

9 10
 Graph (III) 13

Rooted tree: terms

1

2 3

4 5 6

Leaves 7 8

9 10
 Graph (III) 14

Rooted tree: terms

Depth = 0 1

Depth = 1 2 3

Depth = 2 4 5 6 Height = 4

Depth = 3 7 8

Depth = 4 9 10
 Graph (III) 15

Tree: implementation
● Trees are graph so the Node Parent Child[0] Child[1]
same representations
1
1 2 3
are used. 2 1 4 5
3 1 6 2 3
○ e.g. adjacency matrix,
4 2
adjacency list, edge
5 2 7 8 4 5 6
list 6 3
● For rooted tree, we can 7 5 7 8
choose to store the 8 5 9 10
parent and children 9 8
9 10
10 8
separately.
 Graph (III) 16

Tree: application
Some graph problems are trivial in trees.
● Shortest path between two nodes → the only path between two nodes
● Minimum spanning tree → the tree itself
Trees are also used in data structures.
● Binary search tree
● Heap
● Trie
● Segment Tree
● Suffix Tree
 Graph (III) 17

Binary Tree
 Graph (III) 18

Binary Tree
A rooted tree where all vertices (nodes) have at most 2 children.
 Graph (III) 19

Perfect Binary Tree

A rooted tree where all vertices (nodes) have 2 children and all leaves have the
same depth.
 Graph (III) 20

Complete Binary Tree

A perfect binary tree with some or all rightmost leaf nodes removed.
 Graph (III) 21

Tree traversal
 Graph (III) 22

Tree traversal
We can perform DFS on trees as we void dfs(int node) {
for (auto child : children[node])
do on graph. dfs(child);
}

2 3

4 5 6

7 8
 Graph (III) 23

Tree traversal orders

For binary trees, there are 3 common traversal orders:
Pre-order, in-order and post-order.

2 3

Pre-order 1 2 4 5 7 8 3 6
4 5 6
In-order 4 2 7 5 8 1 3 6

7 8 Post-order 4 7 8 5 2 6 3 1
 Graph (III) 24

Pre-order
1 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 25

Pre-order
1 2 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 26

Pre-order
1 2 4 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 27

Pre-order
1 2 4 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 28

Pre-order
1 2 4 5 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 29

Pre-order
1 2 4 5 7 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 30

Pre-order
1 2 4 5 7 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 31

Pre-order
1 2 4 5 7 8 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 32

Pre-order
1 2 4 5 7 8 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 33

Pre-order
1 2 4 5 7 8 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 34

Pre-order
1 2 4 5 7 8 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 35

Pre-order
1 2 4 5 7 8 3 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 36

Pre-order
1 2 4 5 7 8 3 6 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 37

Pre-order
1 2 4 5 7 8 3 6 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 38

Pre-order
1 2 4 5 7 8 3 6 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 39

Pre-order
1 2 4 5 7 8 3 6 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 40

Pre-order
1 2 4 5 7 8 3 6 void preorder_traversal(int node) {
process(node);

if (left_child[node])
preorder_traversal(left_child[node]);
1
if (right_child[node])
preorder_traversal(right_child[node]);
}
2 3

4 5 6 Can imagine each node has a left bar

stuck out. Start a “tour” around the
graph and append the node to the
7 8
answer when encountering a bar.
 Graph (III) 41

In-order
void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 42

In-order
void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 43

In-order
4 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 44

In-order
4 2 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 45

In-order
4 2 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 46

In-order
4 2 7 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 47

In-order
4 2 7 5 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 48

In-order
4 2 7 5 8 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 49

In-order
4 2 7 5 8 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 50

In-order
4 2 7 5 8 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 51

In-order
4 2 7 5 8 1 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 52

In-order
4 2 7 5 8 1 3 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 53

In-order
4 2 7 5 8 1 3 6 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 54

In-order
4 2 7 5 8 1 3 6 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 55

In-order
4 2 7 5 8 1 3 6 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 56

In-order
4 2 7 5 8 1 3 6 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6

7 8
 Graph (III) 57

In-order
4 2 7 5 8 1 3 6 void inorder_traversal(int node) {
if (left_child[node])
inorder_traversal(left_child[node]);

process(node);
1
if (right_child[node])
inorder_traversal(right_child[node]);
}
2 3

4 5 6 Same thing goes for in-order traversal,

but with the bar stuck out at the
bottom.
7 8
 Graph (III) 58

Post-order
void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 59

Post-order
void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 60

Post-order
4 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 61

Post-order
4 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 62

Post-order
4 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 63

Post-order
4 7 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 64

Post-order
4 7 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 65

Post-order
4 7 8 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 66

Post-order
4 7 8 5 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 67

Post-order
4 7 8 5 2 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 68

Post-order
4 7 8 5 2 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 69

Post-order
4 7 8 5 2 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 70

Post-order
4 7 8 5 2 6 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 71

Post-order
4 7 8 5 2 6 3 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 72

Post-order
4 7 8 5 2 6 3 1 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6

7 8
 Graph (III) 73

Post-order
4 7 8 5 2 6 3 1 void postorder_traversal(int node) {
if (left_child[node])
postorder_traversal(left_child[node]);

if (right_child[node])
1 postorder_traversal(right_child[node]);

process(node);
}
2 3

4 5 6 Same thing goes for in-order traversal,

but with the bar stuck out at the right.
7 8
 Graph (III) 74

Breadth-first search on tree

1 2 3 4 5 6 7 8 void bfs(int root) {
queue<int> q;
q.push(root);
while (!q.empty()) {
1 int node = q.front();
q.pop();
for (auto child : children[node])
q.push(child);
2 3 }
}

4 5 6

7 8
 Graph (III) 75

Pre-order, in-order and post-order: applications

A binary tree can be uniquely determined by (pre-order, in-order) or
(post-order, in-order), but not (pre-order, post-order).
1
[HKOJ 01040 Tree Recovery]

2 3

Pre-order 1 2 4 5 7 8 3 6
4 5 6
In-order 4 2 7 5 8 1 3 6

Post-order 4 7 8 5 2 6 3 1 7 8
 Graph (III) 76

Pre-order, in-order and post-order: applications

Most often combined with tree DPs
Problem 1:
Given a rooted tree with N nodes (node 1, 2, …, N), find the size of all N
subtrees with node i as root.
1 ≤ N ≤ 105
 Graph (III) 77

Pre-order, in-order and post-order: applications

Problem 1 Solution: vector<int> size;
vector<vector<int>> children;
We can write a DFS similar to void dfs(int node) {
post-order traversal to calculate the size[node] = 1;
for (auto child : children[node]) {
size of subtree dfs(child);
size[node] += size[child];
size[i] = 1 + sum of size[c] }
}
where c are all children of node i.
 Graph (III) 78

Pre-order, in-order and post-order: applications

Problem 2:
Given a rooted tree with N nodes (node 1, 2, …, N) having initial value 0, there
are two types of operation:
● update(k, v): add v to every node in the subtree of node k
● query(x): answer the value of node x.
Perform all Q operations.
1 ≤ N, Q ≤ 105
 Graph (III) 79

Pre-order, in-order and post-order: applications

Problem 2 Solution:
Store the value of nodes in an array using pre-order of the tree.
Then values of nodes in a subtree is contiguous in the array.
This reduces the problem to range update, point query problem, which can
be solved with data structures like segment tree. 1

For example, the subtree of node 2 is shown below:

2 3
Index 0 1 2 3 4 5 6 7
Pre-order 1 2 4 5 7 8 3 6
Value 0 0 0 0 0 0 0 0 4 5 6

width = subtree size

7 8
 Graph (III) 80

Pre-order, in-order and post-order: applications

Problem 3: (Knapsack on Tree)
Given a rooted tree with N nodes (node 1, 2, …, N), each edge has a digging
cost and each node has a reward.
You can dig some edges such that all digged edges are connected to node 1
by some digged edges. The sum of digging costs cannot exceed a digging
budget B. Find the maximum sum of rewards of nodes lying on any digged
edge.
1 ≤ N, B ≤ 103
(from https://codeforces.com/blog/entry/13168)
 Graph (III) 81

Pre-order, in-order and post-order: applications

Problem 3 Solution:
● DP State?
● dp[i][j] = the maximum reward we can get, if we
consider the subtree at i with digging cost j, if all
digged paths are connected to i
● Combine the children by usual knapsack transition
○ dp[i][j+w(i,ch)] = max(dp[i][j+w(i,ch)], dp[ch][j])+v(i), ch=child
 Graph (III) 82

Pre-order, in-order and post-order: applications

Problem 3 Solution:
● dp[i][j+w(i,ch)] = max(dp[i][j+w(i,ch)], dp[ch][j])+v(i),
ch=child
● As we can see, dp[ch] is required to calculate dp[j]
● This is… post-order!
● We process children first before processing the
node itself
 Graph (III) 83

Pre-order, in-order and post-order: applications

Problem 3 Solution: void dfs(int node, int parent) {
for (auto child : graph[node]) {
● dp[i][j+w(i,ch)] = if (child == parent) continue;

max(dp[i][j+w(i,ch)], dp[ch][j]+v(i)), dfs(child, node);

for (int j = 0; j < B; ++j) {
ch=child dp[node][j + w(node,child)] = max(
● As we can see, dp[ch] is required dp[node][j + w(node,child)],
to calculate dp[i] dp[child][j] + v(child)
);
● This is… post-order! }
● We process children first before }
processing the node itself }
 Graph (III) 84

Tree diameter
 Graph (III) 85

Tree diameter
The diameter of a tree is the furthest distance between
any two nodes in the tree.
For example, in the tree on the right, the diameter of
the tree is 5.
 Graph (III) 86

Tree diameter: algorithm

It is obvious that we can run DFS/BFS from every node once and take the
maximum distance from each run, resulting in an algorithm with complexity
O(V2), where V is the number of nodes.
However, we can do better.
 Graph (III) 87

Tree diameter: algorithm

We do not have to run a DFS/BFS from every node: we only need to do it
twice.
● First, we run a DFS/BFS from any node, recording the depth of each node
from the starting node.
● Among all the nodes with the maximum depth, choose any of them, and
run another DFS/BFS while recording the depth of each node.
● The maximum depth in the second DFS/BFS is the tree diameter.
This results in an algorithm with time complexity O(V), where V is the number
of nodes.
 Graph (III) 88

Tree diameter: implementation

void dfs(int u, int parent, int depth) {
if (max_depth < depth) {
deepest_node = u;
max_depth = depth;
}
for (auto v : edges[u])
if (v != parent) dfs(v, u, depth + 1);
}

int diameter() {
max_depth = 0;
dfs(1, -1, 0);
max_depth = 0;
dfs(deepest_node, -1, 0);
return max_depth;
}
 Graph (III) 89

Tree diameter: proof

How does it work?
Proof by contradiction:
Assume the longest path is not from the deepest node from the root, you can
always extend the path by changing one side to the deepest node
 Graph (III) 90

Tree diameter: example 1

First, we run a DFS from node 1. (This can be from any node.)
First DFS
1
Node 1 2 3 4 5 6 7 8
Depth 0 1 1 2 2 2 3 3
2 3

4 5 6

7 8
 Graph (III) 91

Tree diameter: example 1

As node 7 and 8 have the same, maximum depth, we can choose any of them.
Here, we start from node 7.
1
First DFS
Node 1 2 3 4 5 6 7 8
2 3
Depth 0 1 1 2 2 2 3 3

Second DFS
4 5 6
Node 1 2 3 4 5 6 7 8
Depth 3 2 4 3 1 5 0 2
7 8
 Graph (III) 92

Tree diameter: example 2

First, we run a DFS from node 4. (This can be from any node.)
First DFS
1
Node 1 2 3 4 5 6 7 8
Depth 2 1 3 0 2 4 3 3
2 3

4 5 6

7 8
 Graph (III) 93

Tree diameter: example 2

As node 6 is the deepest node, we start from node 6.
First DFS
1
Node 1 2 3 4 5 6 7 8
Depth 2 1 3 0 2 4 3 3
2 3
Second DFS
Node 1 2 3 4 5 6 7 8
4 5 6
Depth 2 3 1 4 4 0 5 5

7 8
 Graph (III) 94

Lowest common ancestor (LCA)

 Graph (III) 95

Lowest common ancestor (LCA)

● In a rooted tree, the lowest common ancestor of 1
two nodes u and v is the node that is the ancestor
of both u and v and has the highest depth. 2 3
● If one of the nodes is the ancestor of another, it is
the LCA. 4 5 6
● e.g. LCA(4, 8) = 2 (as shown on the right)
LCA(5, 7) = 5 7 8
 Graph (III) 96

Lowest common ancestor (LCA)

Naive solution: 1

1. Check the ancestors of the given nodes and return

2 3
the lowest common one
○ Time complexity per query: O(N)
○ Space complexity: O(1) 4 5 6

2. Precompute the answers of all pairs by running DFS

on each node 7 8
○ Time complexity per query: O(1)
○ Time complexity for precomputation: O(N2)
○ Space complexity: O(N^2)
 Graph (III) 97

Lowest common ancestor (LCA)

Solution 1: 1

● Perform DFS once to generate “Euler tour” of the

2 3
tree:
○ Insert node once when first visiting the node
○ Insert node once when one of its children has been 4 5 6
visited
○ Insert node once when leaving the node 7 8

1 2 4 4 2 5 7 7 5 8 8 5 2 1 3 6 6 3 1
 Graph (III) 98

Lowest common ancestor (LCA)

Solution 1: 1

● For each node, compute the depth and first

2 3
occurrence of the node.
● The LCA always appear between them in the euler
6
tour. 4 5

● The one with the smallest depth is the LCA.

7 8

1 2 4 4 2 5 7 7 5 8 8 5 2 1 3 6 6 3 1

0 1 2 2 1 2 3 3 2 3 3 2 1 0 1 2 2 1 0
 Graph (III) 99

Lowest common ancestor (LCA)

Solution 1:
● Thus the problem is reduced to Range Minimum Query problem
● Can be solved with segment tree or sparse table
● Complexity:
○ Time, precomputation: O(N) for segment tree, O(N log N) for sparse table
○ Time, query: O(log N) for segment tree, O(1) for sparse table
○ Space: O(N) for segment tree, O(N log N) for sparse table

1 2 4 4 2 5 7 7 5 8 8 5 2 1 3 6 6 3 1

0 1 2 2 1 2 3 3 2 3 3 2 1 0 1 2 2 1 0
 Graph (III) 100

Lowest common ancestor (LCA)

Solution 1: 1

● For each node, compute the depth and first

2 3
occurrence of the node.
● The LCA always appear between them in the euler
6
tour. 4 5

● The one with the smallest depth is the LCA.

7 8

● Time complexity: O(N log N + Q), Q = no. of queries

● Space complexity: O(N log N)
 Graph (III) 101

Lowest common ancestor (LCA)

Solution 2: 1

● We can attempt to optimize the naive solution of

checking all ancestors with binary lifting. 2 3

● From now on, let us denote ancestor(u, k) as the

k-th ancestor of node u. 4 5 6
● For example, ancestor(8, 1) = 5,
ancestor(5, 2) = 1, ancestor(2, 3) = 1* 7 8
● (For simplicity, we assume the parent of the root
node to be itself.)
 Graph (III) 102

Lowest common ancestor (LCA)

Solution 2: 1

● First we precompute a table of

ancestor(u, 2i) for i = 0, 1, 2, …, ⌊log2V⌋
2 3

○ ancestor(u, 20 = 1) = the parent of u

○ ancestor(u, 2i + 1) = ancestor(ancestor(u, 2i), 2i) 4 5 6

● We can compute the table in O(N log N).

7 8

Node 1 2 3 4 5 6 7 8
i=0 1 1 1 2 2 3 5 5
i=1 1 1 1 1 1 1 2 2
i=2 1 1 1 1 1 1 1 1
i=3 1 1 1 1 1 1 1 1
 Graph (III) 103

Lowest common ancestor (LCA)

Solution 2: 1

● With the table precomputed, we can find

2 3
ancestor(u, x) in O(log N).
● For example,
6
ancestor(u, 11(10) = 1011(2)) 4 5

= ancestor(ancestor(ancestor(u, 23), 21), 20)

7 8

Node 1 2 3 4 5 6 7 8
i=0 1 1 1 2 2 3 5 5
i=1 1 1 1 1 1 1 2 2
i=2 1 1 1 1 1 1 1 1
i=3 1 1 1 1 1 1 1 1
 Graph (III) 104

Lowest common ancestor (LCA)

Solution 2: 1

● We will call the nodes u, v and assume

2 3
depth[u] ≥ depth[v].
● First, move u to the same level as v by
6
u ← ancestor(u, depth[v] - depth[u]) 4 5

● Then, we can use binary lifting to move u and v to

be one level below the LCA of u and v. 7 8

Node 1 2 3 4 5 6 7 8
i=0 1 1 1 2 2 3 5 5
i=1 1 1 1 1 1 1 2 2
i=2 1 1 1 1 1 1 1 1
i=3 1 1 1 1 1 1 1 1
 Graph (III) 105

Lowest common ancestor (LCA)

Solution 2: 1

● The algorithm is as follows:

for i = ⌊log2V⌋, ⌊log2V⌋ - 1, …, 1, 0: 2 3
if ancestor(u, 2i) ≠ ancestor(v, 2i):
u ← ancestor(u, 2i) 4 5 6
v ← ancestor(v, 2i)
● After this, the parent of u = the parent of v is the 7 8
LCA of u and v.
Node 1 2 3 4 5 6 7 8
i=0 1 1 1 2 2 3 5 5
i=1 1 1 1 1 1 1 2 2
i=2 1 1 1 1 1 1 1 1
i=3 1 1 1 1 1 1 1 1
 Graph (III) 106

Lowest common ancestor (LCA)

Solution 2: 1

● For example, when u = 5 and v = 6,

● ancestor(u, 23) = 1, ancestor(v, 23) = 1 ⇒ no change 2 3
● ancestor(u, 22) = 1, ancestor(v, 22) = 1 ⇒ no change
● ancestor(u, 21) = 1, ancestor(v, 21) = 1 ⇒ no change 4 5 6
● ancestor(u, 20) = 2, ancestor(v, 20) = 3
⇒ u ← ancestor(u, 20), v ← ancestor(u, 20) 7 8
● Now u = 2, v = 3 and parent(u) = parent(v) = 1, which is the
LCA of 5 and 6. Node 1 2 3 4 5 6 7 8
i=0 1 1 1 2 2 3 5 5
i=1 1 1 1 1 1 1 2 2
i=2 1 1 1 1 1 1 1 1
i=3 1 1 1 1 1 1 1 1
 Graph (III) 107

Lowest common ancestor (LCA)

Solution 2: proof for correctness
● Assume the LCA of u and v is ancestor(u, k), and depth[u] = depth[v]
○ i.e. we have already lifted u to the same depth as v
● ancestor(u, a + b) = ancestor(ancestor(u, a), b) for all node u, a ≥ 0, b ≥ 0
○ ancestor(u, 0) = u
● For all i < k, ancestor(u, i) ≠ ancestor(v, i) because of contradiction (lowest common
ancestor)
● For all i ≥ k, ancestor(u, i) = ancestor(ancestor(u, k), i - k)
ancestor(v, i) = ancestor(ancestor(v, k), i - k)
As ancestor(u, k) = ancestor(v, k) and i - k ≥ 0, ancestor(u, i) = ancestor(v, i)
● i.e. the function f(x) = if ancestor(u, x) = ancestor(v, x) then 1 else 0 is increasing
or, in other words, you can binary search on f(x)
 Graph (III) 108

Lowest common ancestor (LCA)

Solution 2: 1

● Time complexity:
2 3
○ Precomputation: O(N log N)
○ Query: O(log N)
6
● Space complexity: O(N log N) 4 5

7 8

Node 1 2 3 4 5 6 7 8
i=0 1 1 1 2 2 3 5 5
i=1 1 1 1 1 1 1 2 2
i=2 1 1 1 1 1 1 1 1
i=3 1 1 1 1 1 1 1 1
 Graph (III) 109

Lowest common ancestor (LCA)

const int N = 1e5 + 10, K = 20; int lca(int u, int v) {
vector<int> g[N]; if (dep[u] < dep[v]) swap(u, v);
int p[N][K], dep[N]; for (int i = K-1; i >= 0; --i) {
void dfs(int u, int par) { int w = p[u][i];
for (int v : g[u]) { if (dep[w] >= dep[v]) u = w;
if (v == par) continue; }
p[v][0] = u; if (u == v) return u;
for (int i = 1; i < K; ++i) { for (int i = K-1; i >= 0; --i) {
p[v][i] = p[p[v][i - 1]][i - 1]; int w = p[u][i], x = p[v][i];
} if (w != x) u = w, v = x;
dep[v] = dep[u] + 1; }
dfs(v, u); return p[u][0];
} }
}
 Graph (III) 110

Lowest common ancestor (LCA): application

Given a unrooted tree, answer distance between two 1
given nodes.
2 3
e.g. query(1, 2) = 1, query(5, 6) = 4

4 5 6

7 8
 Graph (III) 111

Lowest common ancestor (LCA): application

Answer: 1

Pick any node as the root. Then,

2 3
query(u, v)
= (depth[u] - depth[m]) + (depth[v] - depth[m])
4 5 6
where m is the LCA of u and v
We can use any of the methods to compute LCA introduced 7 8
just now.
Note: we can use a similar method to handle path queries
besides distance if the information doesn’t change.
 Graph (III) 112

DAG and Topological Sort

 Graph (III) 113

DAG and Topological Sort

● Directed Acyclic Graph (DAG) is a directed graph with no cycles.
● A rooted tree is also a DAG.

3
4 1

5 2
 Graph (III) 114

Topological Sort
● A topological ordering is an order of vertices in a graph where
if there is an edge A → B, then A appears before B.
● For example, in the graph on the right, one of the
6
topological orderings is
[4, 5, 1, 6, 3, 2] 3
4
● A graph has a topological ordering 1

if and only if the graph is a DAG.

● A graph can have more than one topological ordering. 5 2

For example, [4, 1, 5, 3, 2, 6] is also a valid topological ordering for the

graph.
 Graph (III) 115

Topological Sort
● To obtain a topological order, vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
we can repeat the process of vector<int> topological_sort() {
int n = edge_list.size();
removing nodes with no for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
incoming edges and all edges for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
from that node. vector<int> order;
while (!q.empty()) {
● The code is shown on the right. int u = q.front();
q.pop();
● We will demonstrate with order.push_back(u);
for (auto v : edges[u]) {
samples below. in_drgree[v]--;
if (in_drgree[v] == 0) q.push(v);
}
}
return order;
}
 Graph (III) 116

Topological Sort: Example 1

● First, the in-degree is vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
calculated. vector<int> topological_sort() {
int n = edge_list.size();
for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 1 3 1 0 1 1 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue }
}
2 return order;
Order 5 }
 Graph (III) 117

Topological Sort: Example 1

● Then, the node(s) with no vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
incoming edges are pushed vector<int> topological_sort() {
int n = edge_list.size();
into the queue. for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 1 3 1 0 1 1 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 }
}
2 return order;
Order 5 }
 Graph (III) 118

Topological Sort: Example 1

● Then, we repeat the process of vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
removing nodes in the queue vector<int> topological_sort() {
int n = edge_list.size();
and pushing new nodes with no for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
incoming edges into the queue. for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 0 3 1 0 0 1 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 1 5 }
}
2 return order;
Order 4 5 }
 Graph (III) 119

Topological Sort: Example 1

● Then, we repeat the process of vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
removing nodes in the queue vector<int> topological_sort() {
int n = edge_list.size();
and pushing new nodes with no for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
incoming edges into the queue. for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 0 2 0 0 0 0 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 1 5 3 6 }
}
2 return order;
Order 4 1 5 }
 Graph (III) 120

Topological Sort: Example 1

● Then, we repeat the process of vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
removing nodes in the queue vector<int> topological_sort() {
int n = edge_list.size();
and pushing new nodes with no for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
incoming edges into the queue. for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 0 1 0 0 0 0 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 1 5 3 6 }
}
2 return order;
Order 4 1 5 5 }
 Graph (III) 121

Topological Sort: Example 1

● Then, we repeat the process of vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
removing nodes in the queue vector<int> topological_sort() {
int n = edge_list.size();
and pushing new nodes with no for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
incoming edges into the queue. for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 0 0 0 0 0 0 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 1 5 3 6 2 }
}
2 return order;
Order 4 1 5 3 5 }
 Graph (III) 122

Topological Sort: Example 1

● Then, we repeat the process of vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
removing nodes in the queue vector<int> topological_sort() {
int n = edge_list.size();
and pushing new nodes with no for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
incoming edges into the queue. for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 0 0 0 0 0 0 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 1 5 3 6 2 }
}
2 return order;
Order 4 1 5 3 6 5 }
 Graph (III) 123

Topological Sort: Example 1

● The process is finished when vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
the queue is empty. vector<int> topological_sort() {
int n = edge_list.size();
for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 0 0 0 0 0 0 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 1 5 3 6 2 }
}
2 return order;
Order 4 1 5 3 6 2 5 }
 Graph (III) 124

Topological Sort: Example 1

● The process is finished when vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
the queue is empty. vector<int> topological_sort() {
int n = edge_list.size();
for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 0 0 0 0 0 0 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 1 5 3 6 2 }
}
2 return order;
Order 4 1 5 3 6 2 5 }
 Graph (III) 125

Topological Sort: Example 2

● First, the in-degree is vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
calculated. vector<int> topological_sort() {
int n = edge_list.size();
for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 1 1 1 0 2 1 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 }
}
2 return order;
Order 5 }
 Graph (III) 126

Topological Sort: Example 2

● Then, the node(s) with no vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
incoming edges are pushed vector<int> topological_sort() {
int n = edge_list.size();
into the queue. for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 1 1 1 0 2 1 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 }
}
2 return order;
Order 5 }
 Graph (III) 127

Topological Sort: Example 2

● Then, we repeat the process of vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
removing nodes in the queue vector<int> topological_sort() {
int n = edge_list.size();
and pushing new nodes with no for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
incoming edges into the queue. for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 1 1 1 0 2 1 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 }
}
2 return order;
Order 4 5 }
 Graph (III) 128

Topological Sort: Example 2

● The queue is empty, but we vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
have not processed the whole vector<int> topological_sort() {
int n = edge_list.size();
graph. This means the graph for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;
has a cycle. for (int i = 0; i < n; i++)
if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 1 1 1 0 2 1 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 }
}
2 return order;
Order 4 5 }
 Graph (III) 129

Topological Sort: Example 2

We can use topological
vector<pair<int, int>> edge_list;
vector<vector<int>> edges;
vector<int> topological_sort() {

sort to detect cycles in

int n = edge_list.size();
for (auto [u, v] : edge_list) in_drgree[v]++;
queue<int> q;

a directed graph! for (int i = 0; i < n; i++)

if (in_drgree[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
6 int u = q.front();
Node 1 2 3 4 5 6 q.pop();
order.push_back(u);
In-degree 1 1 1 0 2 1 3 for (auto v : edges[u]) {
4 in_drgree[v]--;
1 if (in_drgree[v] == 0) q.push(v);
Queue 4 }
}
2 return order;
Order 4 5 }
 Graph (III) 130

Practice Problems
● HKOJ 01038 - Preorder Tree Traversal
● HKOJ 01039 - Postorder Tree Traversal
● HKOJ S042 - Teacher’s Problem
● HKOJ M0642 - Cells
● HKOJ T114 - Current Flow
● HKOJ T172 - City Reform
● HKOJ I1311 - Dreaming
● Codeforces 191C - Fools and Roads
● Codeforces 208E - Blood Cousins
● AtCoder nikkei2019_qual_d - Restore the Tree
● AtCoder past201912_k - Conglomerate
 Graph (III) 131

Reference
https://assets.hkoi.org/training2019/g-iii.pdf

https://assets.hkoi.org/training2021/g-iii.pdf

https://assets.hkoi.org/training2022/g-iii.pdf

https://assets.hkoi.org/training2023/g-iii.pdf

https://codeforces.com/blog/entry/13168