Trees appear everywhere in CP: organizational hierarchies, file systems, game trees, and as subproblems in graph algorithms. A tree with n nodes has exactly n-1 edges and a unique path between any two nodes.Analogy: A tree is a family genealogy chart. There is one ancestor at the top (the root), each person has exactly one parent (except the root), and there are no marriages within the family (no cycles). The unique path between any two people goes up to their lowest common ancestor, then down.Key properties to internalize:
n nodes, n-1 edges, always connected, no cycles
Removing any edge splits the tree into exactly two components
// Most common: Adjacency list (unrooted tree)int n;vector<vector<int>> adj(n + 1);for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u);}// Rooted tree: Store parent and childrenvector<int> parent(n + 1);vector<vector<int>> children(n + 1);void root(int u, int p) { parent[u] = p; for (int v : adj[u]) { if (v != p) { children[u].push_back(v); root(v, u); } }}
Converts tree to array for range queries on subtrees. This is one of the most important techniques in tree problems.The Insight: When you run DFS, you visit each node’s subtree contiguously. If you record the entry time tin[u] and exit time tout[u], then the subtree of u occupies a contiguous range [tin[u], tout[u]) in the Euler order. This means you can answer subtree queries (sum, min, max of values in u’s subtree) using a segment tree or BIT over the flattened array.Visual Example for tree with root 1, children 2 and 3, where 2 has children 4 and 5:
vector<int> tin(n + 1), tout(n + 1);vector<int> euler; // Nodes in DFS orderint timer = 0;void eulerTour(int u, int p) { tin[u] = timer++; // Record entry time euler.push_back(u); for (int v : adj[u]) { if (v != p) { eulerTour(v, u); } } tout[u] = timer; // tout[u] = tin[u] + subtreeSize[u]}// Subtree of u corresponds to euler[tin[u]...tout[u]-1]// To query subtree sum: segTree.query(tin[u], tout[u] - 1)
Application: Range queries on subtrees using segment trees. Update a node’s value at position tin[u] in the segment tree, and query subtree sums over [tin[u], tout[u]-1].
Problem: Find the longest path in a tree. The tree diameter is the number of edges on the longest path between any two nodes.Why the double-BFS trick works: Starting from any node, the farthest node from it must be an endpoint of some diameter. This is provable by contradiction: if the farthest node were not a diameter endpoint, there would exist a longer path, contradicting that our node was farthest. So BFS from any start gives one diameter endpoint, and BFS from that endpoint gives the other.
Precompute ancestors at powers of 2 for O(log n) queries.
const int LOG = 20;vector<vector<int>> up(n + 1, vector<int>(LOG));vector<int> depth(n + 1);void preprocess(int root) { // BFS to compute depth and first ancestor queue<int> q; q.push(root); depth[root] = 0; up[root][0] = root; // Parent of root is itself while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (depth[v] == 0 && v != root) { depth[v] = depth[u] + 1; up[v][0] = u; q.push(v); } } } // Build sparse table for (int j = 1; j < LOG; j++) { for (int i = 1; i <= n; i++) { up[i][j] = up[up[i][j-1]][j-1]; } }}int lca(int u, int v) { // Make u the deeper node if (depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; // Lift u up to same depth as v for (int j = 0; j < LOG; j++) { if ((diff >> j) & 1) { u = up[u][j]; } } if (u == v) return u; // Binary search for LCA for (int j = LOG - 1; j >= 0; j--) { if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; } } return up[u][0];}int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)];}
// Example: Count nodes in each subtree with value > thresholdvector<int> subtreeCount(n + 1);void dfs(int u, int p) { subtreeCount[u] = (val[u] > threshold) ? 1 : 0; for (int v : adj[u]) { if (v != p) { dfs(v, u); subtreeCount[u] += subtreeCount[v]; } }}
Problem: Compute answer for each node as if it were the root. A naive approach would run a separate DFS for each root—O(n^2) total. Rerooting DP does it in O(n) with two DFS passes.The Trick: First compute the answer for one root (say node 1) using a standard DFS. Then, in a second DFS, “re-root” the tree to each child by adjusting the parent’s answer. When we move the root from u to its child v, the distances to nodes in v’s subtree decrease by 1 each, while distances to all other nodes increase by 1 each.
// Example: Sum of distances from each node to all other nodesvector<long long> down(n + 1); // Sum of distances to subtreevector<long long> up(n + 1); // Sum of distances to non-subtreevector<int> sz(n + 1);void dfs1(int u, int p) { // Compute down[u] and sz[u] sz[u] = 1; down[u] = 0; for (int v : adj[u]) { if (v != p) { dfs1(v, u); sz[u] += sz[v]; down[u] += down[v] + sz[v]; } }}void dfs2(int u, int p) { // Compute up[u] for (int v : adj[u]) { if (v != p) { // up[v] = up[u] + (contribution from u's other children) // + distance to u + (n - sz[v]) nodes above v up[v] = up[u] + down[u] - down[v] - sz[v] + (n - sz[v]); dfs2(v, u); } }}// Answer for node u = down[u] + up[u]
Problem: Efficiently answer path queries on trees.The centroid is a node whose removal leaves no subtree larger than n/2. Every tree has at least one centroid, and at most two.Analogy: The centroid is the “center of gravity” of the tree. If you tried to balance the tree on a single node like a mobile, the centroid is where it balances — no side is too heavy.Why it works for path queries: After finding the centroid and removing it, the tree splits into subtrees of size at most n/2. We solve for all paths through the centroid, then recursively solve each subtree. Since subtrees are at most half the size, there are at most O(log n) levels of recursion, giving O(n log n) total work for many problems.When to use: Path queries that involve counting or aggregation (paths of length k, closest pair in tree, etc.) where direct LCA-based solutions would be too slow.
vector<int> subtree(n + 1);vector<bool> removed(n + 1, false);int getSubtree(int u, int p) { subtree[u] = 1; for (int v : adj[u]) { if (v != p && !removed[v]) { subtree[u] += getSubtree(v, u); } } return subtree[u];}int getCentroid(int u, int p, int treeSize) { for (int v : adj[u]) { if (v != p && !removed[v] && subtree[v] > treeSize / 2) { return getCentroid(v, u, treeSize); } } return u;}void decompose(int u) { int treeSize = getSubtree(u, -1); int centroid = getCentroid(u, -1, treeSize); removed[centroid] = true; // Process centroid - all paths through centroid // ... for (int v : adj[centroid]) { if (!removed[v]) { decompose(v); } }}
Problem: Aggregate information from children efficiently.
// Example: Count distinct values in each subtreevector<set<int>> nodeSet(n + 1);vector<int> answer(n + 1);void dfs(int u, int p) { nodeSet[u].insert(val[u]); for (int v : adj[u]) { if (v != p) { dfs(v, u); // Merge smaller set into larger if (nodeSet[u].size() < nodeSet[v].size()) { swap(nodeSet[u], nodeSet[v]); } for (int x : nodeSet[v]) { nodeSet[u].insert(x); } nodeSet[v].clear(); } } answer[u] = nodeSet[u].size();}
Complexity: O(n log² n) total due to small-to-large merging.
Problem: Check if two trees have the same structure.
map<vector<int>, int> hashMap;int nextHash = 0;int getHash(int u, int p) { vector<int> childHashes; for (int v : adj[u]) { if (v != p) { childHashes.push_back(getHash(v, u)); } } sort(childHashes.begin(), childHashes.end()); if (hashMap.find(childHashes) == hashMap.end()) { hashMap[childHashes] = nextHash++; } return hashMap[childHashes];}bool isIsomorphic(tree1, tree2) { // Trees are isomorphic if they have same hash when rooted at centroid}