Tree Fundamentals

A tree is a connected acyclic undirected graph. A forest is a disjoint union of trees.

Equivalent definitions

For a graph $G$ on $n$ vertices, any two of the following imply the third — and all five statements are equivalent:

$G$ is connected and acyclic.
$G$ is connected and has exactly $n - 1$ edges.
$G$ is acyclic and has exactly $n - 1$ edges.
Between any two vertices there is exactly one simple path.
$G$ is connected, and removing any edge disconnects it (every edge is a bridge).

Basic facts

Fact
Edges	$n - 1$
Degree sum	$2 (n - 1)$
Leaves	at least 2 (for $n \geq 2$ )
Adding any edge	creates exactly one cycle
Removing any edge	creates exactly two components
Every tree is bipartite	2-colour by depth parity
Labelled trees on $n$ vertices	$n^{n - 2}$ (Cayley, via Prüfer codes)
Forest with $c$ components	$n - c$ edges

Rooting a tree

Most tree algorithms want a root. Pick any vertex (or a center when canonicity matters) and DFS.

vector<int> par, depth, sz;
vector<vector<int>> adj;
 
void dfs(int u, int p) {
    par[u] = p;
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

par, depth and sz are the three arrays nearly every tree algorithm starts from.

Recursion depth
A path-shaped tree with $n = 2 \cdot 1 0^{5}$ will overflow the default stack on some judges. Either write the DFS iteratively or use an explicit stack:
vector<int> order; order.reserve(n);
stack<pair<int,int>> st; st.push({root, -1});
while (!st.empty()) { auto [u,p] = st.top(); st.pop(); par[u]=p; order.push_back(u);
    for (int v : adj[u]) if (v != p) { depth[v]=depth[u]+1; st.push({v,u}); } }
for (int i = order.size()-1; i >= 0; i--) { int u = order[i]; sz[u]=1;
    for (int v : adj[u]) if (v != par[u]) sz[u] += sz[v]; }
Processing order in reverse is a clean way to do “on the way back up” work without recursion.

Traversal orders

Order	When each node is emitted	Use
Preorder	on entry	copying, prefix expressions, Euler tour
Postorder	on exit	subtree aggregation, deletion, tree DP
Inorder	between children (binary trees)	sorted order in a BST
Level order (BFS)	by depth	shortest paths, level statistics

Standard quantities and how to get them

Quantity	Method	Time
Subtree sizes	one DFS, accumulate on exit	$O (n)$
Diameter	two BFS, or one DFS DP	$O (n)$
Center	leaf peeling, or midpoint of the diameter	$O (n)$
Centroid	the vertex whose largest subtree is $\leq n /2$	$O (n)$
LCA	binary lifting or Euler + RMQ	$O (n lo g n)$ / $O (lo g n)$
Distance $u \to v$	$d_{u} + d_{v} - 2 d_{lca}$	$O (lo g n)$
Sum of all pairwise distances	edge contribution: $\sum_{e} s_{e} (n - s_{e})$	$O (n)$
Path max/min	binary lifting or HLD	$O (lo g n)$

The edge-contribution trick

For any edge $e$ splitting the tree into parts of size $s$ and $n - s$ , exactly $s (n - s)$ vertex pairs have their path crossing $e$ . So

$\sum_{u < v} dist (u, v) = \sum_{e} w_{e} s_{e} (n - s_{e}),$

computable in one DFS. This “count the contribution of each edge instead of each path” move solves a whole class of problems.

Centroid

A centroid is a vertex whose removal leaves every component of size $\leq n /2$ . Every tree has one or two, found in one DFS:

int centroid(int u, int p, int n) {
    for (int v : adj[u])
        if (v != p && sz[v] > n / 2) return centroid(v, u, n);
    return u;
}

It is the foundation of centroid decomposition, which is how path-counting problems on trees get an $O (n lo g n)$ solution.

See also: Tree Diameter · Tree DP · Euler Tour

whoashish's cp notes

Directory