Overview
Trees are connected acyclic graphs that appear frequently in competitive programming. This section covers essential tree algorithms for efficient queries and computations.
Tree Diameter
The diameter of a tree is the length of the longest path between any two nodes.
Implementation
const int mxN = 1e5;
int dp[mxN];
int dfs(int node, int parent) {
int mx = 0;
int first = 0, second = 0;
for(int &child: adj[node]) {
if(child == parent) continue;
int factor = dfs(child, node) + 1;
mx = max(mx, factor);
if(factor >= first) {
second = first;
first = factor;
} else if(factor >= second) {
second = factor;
}
}
dp[node] = first + second;
return mx;
}
// Usage:
// n: number of nodes
// dfs(0, 0);
// int diameter = *max_element(dp, dp + n);
Usage Example
const int mxN = 1e5;
vector<int> adj[mxN];
int dp[mxN];
// ... (include dfs function)
int main() {
int n;
cin >> n;
// Read tree edges
for(int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Compute diameter
dfs(0, 0);
int diameter = *max_element(dp, dp + n);
cout << "Tree diameter: " << diameter << "\n";
return 0;
}
Time Complexity: O(N) - Single DFS traversalSpace Complexity: O(N) for adjacency list and dp array
Algorithm Explanation
For each node, we track the two longest paths going down to its children. The diameter passing through that node is the sum of these two longest paths. The overall diameter is the maximum across all nodes.
Binary Lifting
Binary lifting enables O(log N) queries for:
- Lowest Common Ancestor (LCA)
- Jumping k levels up in the tree
- Distance between two nodes
Implementation
const int mxN = 2e5 + 10;
const int LOG = 20;
vector<int> adj[mxN];
int up[mxN][LOG]; // up[node][i] = 2^i-th ancestor of node
int tin[mxN]; // entry time in DFS
int tout[mxN]; // exit time in DFS
int depth[mxN]; // depth of each node
int timer = 0;
void lifting(int node, int parent) {
tin[node] = ++timer;
up[node][0] = parent;
for(int i = 1; i < LOG; ++i) {
up[node][i] = up[up[node][i-1]][i-1];
}
for(auto &child: adj[node]) {
if(child == parent) continue;
depth[child] = depth[node] + 1;
lifting(child, node);
}
tout[node] = ++timer;
}
bool is_ancestor(int left, int right) {
return tin[left] <= tin[right] && tout[left] >= tout[right];
}
int lca(int left, int right) {
if(is_ancestor(left, right)) {
return left;
} else if(is_ancestor(right, left)) {
return right;
}
for(int i = LOG-1; i >= 0; i--) {
if(!is_ancestor(up[left][i], right)) {
left = up[left][i];
}
}
return up[left][0];
}
// Jump k levels up in the tree
int jump(int node, int k) {
for(int i = 0; i < LOG; ++i) {
if((k >> i) & 1 && node != -1) {
node = up[node][i];
}
}
return node;
}
// Distance between 2 nodes -> O(log n)
// depth[left] + depth[right] - 2*depth[lca(left, right)]
// lifting(0, 0); // Initialize from root
Usage Example
int main() {
int n;
cin >> n;
// Build tree
for(int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Preprocess
depth[0] = 0;
lifting(0, 0); // root = 0, parent of root = 0
int q;
cin >> q;
while(q--) {
int u, v;
cin >> u >> v;
// Find LCA
int ancestor = lca(u, v);
// Calculate distance
int dist = depth[u] + depth[v] - 2 * depth[ancestor];
cout << "LCA(" << u << ", " << v << ") = " << ancestor << "\n";
cout << "Distance = " << dist << "\n";
}
return 0;
}
Preprocessing: O(N log N)Query Time: O(log N) for LCA and jump operationsSpace Complexity: O(N log N)
Binary Lifting Functions
- lifting(node, parent): Preprocesses the tree for binary lifting
- is_ancestor(u, v): Checks if u is an ancestor of v in O(1)
- lca(u, v): Finds the lowest common ancestor in O(log N)
- jump(node, k): Jumps k levels up from node in O(log N)
The LOG constant should be set to at least ⌈log₂(max_n)⌉. For n ≤ 200,000, LOG = 20 is sufficient.
Euler Tour
Euler tour flattens a tree into a linear array, enabling range queries using segment trees or other data structures.
Implementation
const int mxN = 2e5 + 10;
vector<int> adj[mxN];
int tour[2 * mxN]; // Euler Tour
int timer = 0;
void eulerTree(int node, int parent) {
tour[timer++] = node;
for(int &child: adj[node]) {
if(child == parent) continue;
eulerTree(child, node);
tour[timer++] = node;
}
}
// Example tree:
// 1
// / \
// 2 3
// / \
// 4 5
// Euler Tour: 1 2 1 3 4 3 5 3 1
Usage Example
int main() {
int n;
cin >> n;
// Build tree
for(int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Generate Euler tour
timer = 0;
eulerTree(0, -1); // root = 0, no parent
// Print tour (size will be 2*n - 1)
cout << "Euler Tour: ";
for(int i = 0; i < 2*n - 1; ++i) {
cout << tour[i] << " ";
}
cout << "\n";
return 0;
}
Time Complexity: O(N)Space Complexity: O(N)The Euler tour has exactly 2N - 1 elements for a tree with N nodes.
Applications of Euler Tour
- Subtree Queries: Subtrees become contiguous ranges
- LCA with RMQ: Reduce LCA to Range Minimum Query
- Path Queries: Enable segment tree operations on tree paths
- Heavy-Light Decomposition: Used in advanced tree decomposition
Advanced Tree Techniques
Tree Flattening for Subtree Queries
int tin[mxN]; // entry time
int tout[mxN]; // exit time
int timer = 0;
void dfs(int node, int parent) {
tin[node] = ++timer;
for(int child : adj[node]) {
if(child == parent) continue;
dfs(child, node);
}
tout[node] = timer;
}
// Subtree of node: [tin[node], tout[node]]
// Check if u is in subtree of v: tin[v] <= tin[u] <= tout[v]
Distance Calculation
With binary lifting preprocessed:
int distance(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
K-th Ancestor
Jumping k levels up:
int kth_ancestor(int node, int k) {
for(int i = 0; i < LOG; ++i) {
if((k >> i) & 1) {
node = up[node][i];
if(node == -1) return -1;
}
}
return node;
}
Complete Example: Tree Queries
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 10;
const int LOG = 20;
vector<int> adj[mxN];
int up[mxN][LOG];
int depth[mxN];
int tin[mxN], tout[mxN];
int timer = 0;
void dfs(int node, int parent) {
tin[node] = ++timer;
up[node][0] = parent;
for(int i = 1; i < LOG; ++i) {
up[node][i] = up[up[node][i-1]][i-1];
}
for(int child : adj[node]) {
if(child == parent) continue;
depth[child] = depth[node] + 1;
dfs(child, node);
}
tout[node] = timer;
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
if(is_ancestor(u, v)) return u;
if(is_ancestor(v, u)) return v;
for(int i = LOG-1; i >= 0; i--) {
if(!is_ancestor(up[u][i], v)) {
u = up[u][i];
}
}
return up[u][0];
}
int distance(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
int main() {
int n, q;
cin >> n >> q;
for(int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
depth[0] = 0;
dfs(0, 0);
while(q--) {
int u, v;
cin >> u >> v;
cout << distance(u, v) << "\n";
}
return 0;
}
Always preprocess trees with DFS before answering queries. Binary lifting is essential for efficient LCA queries in competitive programming.
When using binary lifting with jump operations, initialize with lifting(root, -1) instead of lifting(root, root) if you want jumps beyond the root to return -1.