i. Tree Basics, Diameter and Center

A tree is a connected acyclic graph. These are equivalent for a graph on $n$ vertices: connected and acyclic; connected with $n-1$ edges; acyclic with $n-1$ edges; exactly one simple path between any two vertices; minimally connected (every edge is a bridge); maximally acyclic (any added edge closes exactly one cycle).

Proof: the characterisations

Every connected graph has a spanning tree, and an acyclic graph with $c$ components has $n-c$ edges (add edges one by one: each joins two components since it closes no cycle). So connected + acyclic gives $n-1$ edges; connected with $n-1$ edges: its spanning tree already has $n-1$ edges, so it is the whole graph and acyclic; acyclic with $n-1$ edges has $c=1$ component. Two different paths between $u,v$ contain a cycle (take the first divergence and the next common vertex), and a cycle gives two paths between adjacent cycle vertices, so “unique paths” is acyclic + connected. An edge on a cycle is not a bridge, and a bridge is on no cycle, so “every edge is a bridge” is acyclic + connected. Adding $uv$ to a tree closes exactly the cycle formed with the unique $u$–$v$ path.

Basic facts

Fact
Edges	$n-1$
Degree sum	$2(n-1)$
Leaves	at least 2 (for $n\ge 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’s formula, proved via Prüfer codes in Isomorphism and Prüfer Codes)
Forest with $c$ components	$n-c$ edges

Types of trees

Every later note works with some specialisation of “tree”. This is the map: what each kind actually is, where it is actually used in CP (not just CS theory), and which note implements it. “Free tree” above means no designated root; everything below assumes a root unless noted.

Type	What it is	Used for in CP	Note
Free / rooted tree, forest	connected acyclic graph; a forest is a disjoint union of trees	the base object of this whole chapter	—
Binary tree	each node has $\le 2$ children, distinguished left/right	the shape behind recursion, heaps, Huffman, expression trees	—
Full / complete / perfect binary tree	full: every node has 0 or 2 children; complete: every level full except possibly the last, filled left to right; perfect: every leaf at the same depth, $2^{h+1}-1$ nodes	binary heaps are complete binary trees stored in an array (no pointers, $O(1)$ parent/child index)	Heaps
Binary search tree (BST)	binary tree, in-order = sorted order	the model; almost never hand-rolled unbalanced in CP (worst case $O(n)$ depth)	—
Balanced BST (AVL, red-black, weight-balanced)	BST with a rebalancing invariant bounding height to $O(\log n)$	textbook-important, essentially never implemented from scratch in a contest — std::set/map (red-black internally) or a treap give the same guarantees with far less code	STL Containers
Treap	BST keyed by value, heap-ordered by an independent random priority	the CP balanced BST: split/merge, implicit keys (order statistics without stored keys), persistence	Treaps and Balanced BSTs
Splay tree	BST that rotates the accessed node to the root	amortized $O(\log n)$ with no stored balance info; the link-cut tree’s per-node structure	Treaps and Balanced BSTs, Link-Cut Tree
B-tree / B+-tree	wide-fanout balanced search tree, $O({\log }_{B}n)$ depth	database/filesystem indexing; rare in CP, relevant mainly for external-memory arguments	Treaps and Balanced BSTs
Trie	tree keyed by the characters/bits of a path from the root	string sets with a common-prefix structure, Aho–Corasick, bitwise max-XOR tries	Trie and Aho–Corasick
Cartesian tree	heap-ordered by value, BST-ordered by index, built in $O(n)$ by a monotonic stack	the RMQ $\leftrightarrow$ LCA reduction; “divide at the minimum” recursions	Monotonic Stack, Range Minimum Query
Segment tree / Fenwick tree	an implicit binary tree over array positions (segment tree) or over bit-prefixes (Fenwick), never built as pointers	the default range-query structure; the tree is there for correctness reasoning even though the code has no node objects	Segment Tree, Fenwick Tree
k-d tree	binary tree splitting points by alternating coordinate	nearest-neighbour / orthogonal range queries in low dimensions	KD-Tree and Spatial Structures
Suffix tree	compressed trie of all suffixes of a string	pattern matching, substring structure; usually superseded by the suffix automaton in CP	Suffix Tree
Spanning tree / MST	a tree subgraph touching every vertex of a (connected) graph; MST minimises total weight	connectivity backbones, Kruskal reconstruction trees, network design	Minimum Spanning Trees
Kruskal reconstruction tree	binary tree built by Kruskal’s merge order, internal nodes hold the merging edge’s weight	offline “max edge weight on path $\le x$” / “smallest $x$ connecting $u,v$” queries via LCA	Kruskal Reconstruction Tree
Centroid tree	recursive centroid-decomposition structure, height $O(\log n)$	path-counting problems with an $O(n\log n)$ divide step	Centroid Decomposition
Heavy-light / long-path skeleton	the original tree re-viewed as $O(\log n)$ chains	path queries and updates via segment trees over chains	Heavy-Light Decomposition
Virtual (auxiliary) tree	the Steiner tree of a marked vertex set plus their pairwise LCAs	DP restricted to $k$ marked vertices in $O(k\log n)$ total instead of $O(n)$	Virtual Tree
Link-cut tree	splay-tree-based structure supporting link, cut, path queries on a dynamic forest	dynamic connectivity / path problems where the tree itself changes online	Link-Cut Tree
Euler tour tree	balanced sequence (treap) storing a forest’s Euler tour	dynamic forest connectivity and subtree aggregates under link/cut	Euler Tour Tree
Top tree	hierarchy of clusters built from edges by two merge rules	the most general dynamic-tree structure; path and subtree operations, non-local recombination	Top Trees
Persistent tree (segment tree, treap, trie)	any of the above rebuilt so every update creates $O(\log n)$ new nodes, sharing the rest	”query an old version”, rollback, functional/persistent data structures	Persistence

Proof: node counts for binary trees

A full binary tree with $k$ internal nodes (degree-2) has exactly $k+1$ leaves: induction on $k$ — a single node ($k=0$) has $1=k+1$ leaf, and turning a leaf into an internal node with two new leaves increases both $k$ and the leaf count by one, preserving $k+1$. A perfect binary tree of height $h$ has every level full: level $i$ has $2^i$ nodes (root at $i=0$), so the total is ${\sum }_{i=0}^h{2}^i=2^{h+1}-1$, and all $2^h$ leaves sit at depth $h$. $■$

Rooting without recursion

struct RootedTree {                                     // parent, depth, BFS order, subtree sizes
    int n; vector<vector<int>> adj; vector<int> par, dep, order, sub;
    RootedTree(int n) : n(n), adj(n), par(n, -1), dep(n), sub(n, 1) {}
    void addEdge(int u, int v) { adj[u].push_back(v), adj[v].push_back(u); }
    void root(int r) {
        order = {r}; par[r] = -1; dep[r] = 0;
        for (int i = 0; i < sz(order); i++) for (int v : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], dep[v] = dep[order[i]] + 1, order.push_back(v);
        for (int i = n - 1; i > 0; i--) sub[par[order[i]]] += sub[order[i]];
    }
};

Processing order backwards is a post-order: every child before its parent. Use it for all “on the way up” DP when recursion depth ($n=2\cdot 10^5$ path) is a risk.

Recursion depth

A path-shaped tree with $n=2\cdot 10^5$ overflows the default stack on some judges if rooted recursively. RootedTree::root above is the iterative replacement; use it (or an explicit stack) whenever depth isn’t bounded well below the recursion limit.

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

Edge contribution. An edge whose lower side has $s$ vertices lies on the paths of exactly $s(n-s)$ pairs, so ${\sum }_{u<v}\text{dist}(u,v)={\sum }_e{w}_e{s}_e(n-s_e)$. The same “count per edge, not per path” move handles sums of path lengths over subsets, expected distances, and colour-pair counts.

Diameter

The diameter is the longest simple path between any two vertices — in edges, or in total weight for a weighted tree.

pair<int, ll> farthest(const vector<vector<pair<int, ll>>>& adj, int src, vector<ll>& d) {   // weights >= 0
    int n = sz(adj); d.assign(n, -1); d[src] = 0; vector<int> st{src};
    while (sz(st)) { int u = st.back(); st.pop_back(); for (auto [v, w] : adj[u]) if (d[v] < 0) d[v] = d[u] + w, st.push_back(v); }
    int b = int(max_element(all(d)) - d.begin()); return {b, d[b]};
}
// diameter endpoints a, b: a = farthest(any), b = farthest(a); ecc(v) = max(dist(a, v), dist(b, v))
ll diameterDP(const vector<vector<pair<int, ll>>>& adj, int r = 0) {   // any weights; best path with >= 1 vertex
    int n = sz(adj); vector<int> par(n, -1), order{r}; vector<ll> down(n, 0); ll best = 0;
    for (int i = 0; i < sz(order); i++) for (auto [v, w] : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], order.push_back(v);
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i]; ll d1 = 0, d2 = 0;                       // two best downward extensions (>= 0)
        for (auto [v, w] : adj[u]) if (v != par[u]) { ll d = max(0LL, down[v] + w); if (d > d1) d2 = d1, d1 = d; else if (d > d2) d2 = d; }
        down[u] = d1; best = max(best, d1 + d2);
    }
    return best;
}

• Two sweeps need non-negative weights; the DP works for any weights (it returns the heaviest path, possibly a single vertex).
• Eccentricity of every vertex is $\max (\text{dist}(a,v),\text{dist}(b,v))$ for diameter endpoints $a,b$: two traversals give all of them.
• Joining two trees by one edge to minimise the new diameter: connect their centres; the result is $\max (d_1,d_2,\lceil d_1/2\rceil +\lceil d_2/2\rceil +1)$ (unit weights).
• All diameters share the centre: every diameter passes through the centre(s).
• Two centres iff the diameter has odd length (an even number of vertices on the diameter path); otherwise there is exactly one, the diameter’s midpoint.

Proof: the double sweep and eccentricities (non-negative weights)

Lemma: for any vertex $s$, every farthest vertex $a$ from $s$ ends some diameter. Let $x⇝y$ be a diameter and $c$ the vertex of that path closest to $s$; every path from $s$ to the diameter path enters it at $c$, so $d(s,x)=d(s,c)+d(c,x)$ and likewise for $y$. If the path $s⇝a$ passes through $c$: $d(c,a)\ge \max (d(c,x),d(c,y))$ because $a$ is farthest from $s$. The branch $c⇝a$ leaves $c$ towards at most one of $x,y$, say not towards $x$; then $d(x,a)=d(x,c)+d(c,a)\ge d(x,c)+d(c,y)=d(x,y)$. Otherwise the path $s⇝a$ leaves the path $s⇝c$ at some $m\ne c$ and never meets the diameter path; $d(m,a)\ge d(m,c)+d(c,y)$ by farthestness, so $d(x,a)=d(x,c)+d(c,m)+d(m,a)\ge d(x,y)$ (weights $\ge 0$). Either way $(x,a)$ is a diameter, so the second sweep from $a$ finds the diameter length.

Eccentricity: keep the notation with $s=v$ and $z$ farthest from $v$. In the first case $d(x,z)=d(x,c)+d(c,z)\le d(x,y)$ gives $d(c,z)\le d(c,y)$, so $d(v,z)\le d(v,y)$; in the second, $d(x,z)=d(x,c)+d(c,m)+d(m,z)\le d(x,y)$ gives $d(m,z)\le d(c,y)\le d(m,c)+d(c,y)$, so again $d(v,z)\le d(v,y)$. Hence $\text{ecc}(v)=\max (d(v,x),d(v,y))$ for any fixed diameter $x⇝y$. DP: every path has a unique highest vertex $u$, where it consists of at most two downward branches into different children; down is the best non-negative downward extension, so the maximum over $u$ of $d_1+d_2$ ranges over all paths.

Centre and centroid

	Centre	Centroid
minimises	eccentricity (max distance)	largest remaining component / sum of distances
count	1 or 2 (adjacent)	1 or 2 (adjacent)
find	peel leaves, or middle of a diameter	one DFS on subtree sizes
used for	canonical root, minimum height (= radius $\lceil d/2\rceil$)	centroid decomposition, isomorphism root, the tree median

The centre is the canonical choice when an unrooted tree needs a root for comparison or hashing: it is defined purely by the tree’s structure, so isomorphic trees have corresponding centres, and there are at most two to try — AHU isomorphism testing roots one tree at its centre and tries both centres of the other. Facility location: placing one facility on a tree to minimise the worst-case distance means placing it at the centre (or at the midpoint of the diameter edge itself, if fractional positions are allowed and the diameter has even length).

vector<int> treeCenters(const vector<vector<int>>& adj) {      // peel leaves layer by layer
    int n = sz(adj); if (n == 1) return {0};
    vector<int> deg(n), layer; for (int i = 0; i < n; i++) if ((deg[i] = sz(adj[i])) <= 1) layer.push_back(i);
    for (int removed = sz(layer); removed < n;) {
        vector<int> nxt; for (int u : layer) for (int v : adj[u]) if (--deg[v] == 1) nxt.push_back(v);
        removed += sz(nxt); layer = nxt;
    }
    return layer;
}
vector<int> treeCentroids(const vector<vector<int>>& adj) {
    int n = sz(adj); vector<int> par(n, -1), order{0}, sub(n, 1), res;
    for (int i = 0; i < n; i++) for (int v : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], order.push_back(v);
    for (int i = n - 1; i > 0; i--) sub[par[order[i]]] += sub[order[i]];
    for (int u = 0; u < n; u++) {
        int mx = n - sub[u]; for (int v : adj[u]) if (v != par[u]) mx = max(mx, sub[v]);
        if (2 * mx <= n) res.push_back(u);
    }
    return res;
}

Proof: centres, centroids and the median property

Centre. For $n\ge 3$, a farthest vertex from any $v$ is a leaf, and removing all leaves lowers every remaining eccentricity by exactly one: the neighbour of a farthest leaf survives at distance one less, and no surviving vertex is at the old maximum distance (it would have a farther neighbour). So the vertices of minimum eccentricity are the last to be removed, and peeling ends with one vertex or two adjacent ones. A diameter of length $d$ forces $\text{ecc}\ge \lceil d/2\rceil$ at every vertex (one of its endpoints is that far), and its middle vertex (either middle vertex when $d$ is odd) attains it, since a vertex farther from it would extend half of the diameter beyond $d$. So the radius is $\lceil d/2\rceil$, the centres are the middle of every diameter, and every diameter passes through them. Joining: a path through the new edge has length at most $e_1+1+e_2$ where $e_i$ are the eccentricities of the endpoints, minimised by centres with $e_i=\lceil d_i/2\rceil$, and paths inside one tree keep their lengths.

Centroid. Let $S(u)={\sum }_{x}d(u,x)$. Moving from $u$ to a neighbour $w$ changes $S$ by $(n-s_w)-s_w=n-2s_w$, where $s_w$ is the size of the component of $G-u$ containing $w$. Along any path $u_0,u_1,\dots$ these sizes strictly decrease (each side contains the next), so the increments $n-2s$ strictly increase: $S$ is strictly convex along paths. Therefore $u$ minimises $S$ iff no single step decreases it, iff every component of $G-u$ has $\le n/2$ vertices: centroids are exactly the medians. Convexity also shows the minimisers are connected and that along a path at most one increment is $0$, so there are one or two centroids and two are adjacent. A centroid exists: walk from any vertex into a component of size $>n/2$ while one exists; the part behind has $<n/2$ vertices, so the walk never turns back and stops at a centroid.

Dynamic diameter under weight changes

On the Euler tour with root distances $d$ (vertex appears after each child returns), the diameter is ${\max }_{i\le j\le k}(d_i-2d_j+d_k)$: the middle index plays the LCA. A lazy segment tree keeps $\max d$, $\max (-2d)$, $\max (d_i-2d_j)$, $\max (-2d_j+d_k)$ and the full triple; changing an edge weight adds a constant on the subtree’s tour interval. $O(\log n)$ per update. (CEOI 2019 “Diameter” is the direct showcase for this structure.)

struct DynamicDiameter {                                       // weights >= 0, rooted at 0
    struct Node { ll a, b, ab, bc, abc, lz = 0; };            // max d, max -2d, max d_i-2d_j, max -2d_j+d_k, max triple
    int n, m; vector<int> tin, tout, lower; vector<ll> w; vector<Node> t;
    static Node merge(const Node& x, const Node& y) {
        return {max(x.a, y.a), max(x.b, y.b), max({x.ab, y.ab, x.a + y.b}), max({x.bc, y.bc, x.b + y.a}),
                max({x.abc, y.abc, x.ab + y.a, x.a + y.bc}), 0};
    }
    static void apply(Node& x, ll v) { x.a += v, x.b -= 2 * v, x.ab -= v, x.bc -= v, x.lz += v; }
    DynamicDiameter(int n, const vector<tuple<int, int, ll>>& edges) : n(n), tin(n), tout(n), lower(sz(edges)), w(sz(edges)) {
        vector<vector<pair<int, int>>> adj(n);
        for (int e = 0; e < sz(edges); e++) { auto [u, v, x] = edges[e]; adj[u].push_back({v, e}), adj[v].push_back({u, e}); w[e] = x; }
        vector<ll> tour{0}, d(n); vector<int> it(n), pe(n, -1), st{0};
        while (sz(st)) {
            int u = st.back();
            if (it[u] < sz(adj[u])) {
                auto [v, e] = adj[u][it[u]++];
                if (e == pe[u]) continue;
                pe[v] = e, lower[e] = v, d[v] = d[u] + w[e], tin[v] = sz(tour); tour.push_back(d[v]); st.push_back(v);
            } else { st.pop_back(); tout[u] = sz(tour) - 1; if (sz(st)) tour.push_back(d[st.back()]); }
        }
        m = sz(tour); t.assign(4 * m, Node()); build(1, 0, m, tour);
    }
    void build(int p, int l, int r, const vector<ll>& tour) {
        if (r - l == 1) { ll x = tour[l]; t[p] = {x, -2 * x, -x, -x, 0, 0}; return; }
        int mid = (l + r) / 2; build(2 * p, l, mid, tour); build(2 * p + 1, mid, r, tour); t[p] = merge(t[2 * p], t[2 * p + 1]);
    }
    void add(int p, int l, int r, int x, int y, ll v) {
        if (y <= l || r <= x) return;
        if (x <= l && r <= y) return apply(t[p], v);
        if (t[p].lz) apply(t[2 * p], t[p].lz), apply(t[2 * p + 1], t[p].lz), t[p].lz = 0;
        int mid = (l + r) / 2; add(2 * p, l, mid, x, y, v); add(2 * p + 1, mid, r, x, y, v); t[p] = merge(t[2 * p], t[2 * p + 1]);
    }
    void setWeight(int e, ll nw) { int v = lower[e]; add(1, 0, m, tin[v], tout[v] + 1, nw - w[e]); w[e] = nw; }
    ll diameter() const { return t[1].abc; }
};

Proof: the Euler-tour formula

In this tour, between the positions of any two vertices $u,v$ the minimum depth $d_j$ is attained at their LCA (the walk from $u$ to $v$ climbs to the LCA and never above it), and every position between them has depth at least that. So $d_i-2d_j+d_k\le \text{dist}(u_i,u_k)$ for $i\le j\le k$, with equality when $j$ is the LCA’s position; maximising over all triples gives the maximum distance, which is the diameter (non-negative weights make every $d_i-2d_j+d_k$ a real distance or less). The node fields combine over a split point by case analysis on which of $i,j,k$ lie left or right. Adding $v$ to a subtree’s interval shifts the fields by $v,-2v,-v,-v,0$ respectively (an abc triple fully inside the interval is unchanged by the shift).

Other tools

• Binarisation: replace a vertex with $k>2$ children by a chain of 0-weight dummies, each keeping one child; distances between original vertices are unchanged and every degree is $\le 3$ (needed for edge-centroid decomposition and some top-tree constructions).
• Morris traversal: in-order traversal of a binary tree in $O(1)$ extra space by temporarily threading each in-order predecessor’s empty right pointer back to the node. Variants: visit the node before descending left for pre-order instead of after (in-order); the same thread-rewiring trick underlies $O(1)$-space BST-property validation and flattening a binary tree to a linked list.

template <class T> vector<vector<pair<int, T>>> binarizeTree(const vector<vector<pair<int, T>>>& adj, int root) {
    int n = sz(adj); vector<vector<pair<int, T>>> b(n);
    auto addEdge = [&](int u, int v, T w) { b[u].push_back({v, w}); b[v].push_back({u, w}); };
    vector<int> par(n, -1), order{root}; par[root] = root;
    for (int i = 0; i < sz(order); i++) {
        int u = order[i]; vector<pair<int, T>> ch;
        for (auto [v, w] : adj[u]) if (par[v] == -1) par[v] = u, order.push_back(v), ch.push_back({v, w});
        int last = u;                                           // u keeps ch[0]; a 0-weight dummy chain takes the rest
        for (int j = 0; j < sz(ch); j++) {
            if (j > 0 && j + 1 < sz(ch)) { int d = sz(b); b.emplace_back(); addEdge(last, d, T{}); last = d; }
            addEdge(last, ch[j].first, ch[j].second);
        }
    }
    return b;
}
struct BNode { int val; BNode *left = nullptr, *right = nullptr; };
vector<int> morrisInorder(BNode* cur) {
    vector<int> res;
    while (cur) {
        if (!cur->left) { res.push_back(cur->val); cur = cur->right; continue; }
        BNode* pre = cur->left;
        while (pre->right && pre->right != cur) pre = pre->right;
        if (!pre->right) pre->right = cur, cur = cur->left;               // thread, go left
        else pre->right = nullptr, res.push_back(cur->val), cur = cur->right;   // second visit: unthread
    }
    return res;
}

Proof: binarisation and Morris traversal

Binarisation: each original edge is kept with its weight (child edges hang from $u$ or from dummies on a 0-weight chain below $u$), so every original path maps to a path of the same weight through some dummies, and dummies are never on a path between original vertices except as such chain vertices. Degrees: $u$ keeps its parent, one child and one dummy; a dummy has its predecessor, one child and the next dummy; the last one has its predecessor and at most two children.

Morris: when cur has a left subtree, its in-order predecessor pre is the rightmost node of that subtree. The first time we reach cur, pre->right is empty, we thread it to cur and traverse the left subtree; the in-order traversal of that subtree ends at pre, whose (threaded) right pointer brings us back to cur, where we detect the thread, remove it, output cur and continue right. So the output order is in-order and every thread is removed, restoring the tree. Each edge is walked at most twice to find predecessors (once to create, once to remove the thread) plus once in normal descent: $O(n)$.