Introduction to Tree Algorithms

Trees are generally treated very differently from general graph problems.

Resources

Some properties/definitions of trees:

• A graph is a tree iff it is connected and contains $N$ nodes and $N-1$ edges
• A graph is a tree iff every pair of nodes has exactly one simple path between them
• A graph is a tree iff it is connected and does not contain any cycles

General Tree Terminology:

• A leaf of a tree is any node in the tree with degree $1$
  • If the tree is rooted, the root with a single child is not typically considered a leaf, but depending on the problem, this is not always the case
• A star graph has two common definitions. Try to understand what they mean - they typically appear in subtasks.
  • Definition 1: Only one node has degree greater than $1$
  • Definition 2: Only one node has degree greater than $2$
• A forest is a graph such that each connected component is a tree

Rooted Tree Terminology:

• A root of a tree is any node of the tree that is considered to be at the 'top'
• A parent of a node $n$ is the first node along the path from $n$ to the root
  • The root does not have a parent. This is typically done in code by setting the parent of the root to be $-1$.
• The ancestors of a node are its parent and parent's ancestors
  • Typically, a node is considered its own ancestor as well (such as in the subtree definition)
• The subtree of a node $n$ are the set of nodes that have $n$ as an ancestor
  • A node is typically considered to be in its own subtree
  • Note: This is easily confused with subgraph
• The depth, or level, of a node is its distance from the root

Solution - Subordinates

In this problem we are given the parent of each node of a rooted tree, and we want to compute the subtree size for each node. A subtree is composed of a root node and the subtrees of the root's children. Thus, the size of a subtree is one plus the size of the root's childrens' subtrees.

1#include <bits/stdc++.h>
2using namespace std;
3
4const int SZ = 2e5;
5
6vector<int> children[SZ];
7int subtree_size[SZ], depth[SZ];
8
9void dfs_size(int node) {
10    subtree_size[node] = 1; // This one represents the root of `node's` subtree

1import java.io.*;
2import java.util.*;
3
4public class Subordinates
5{
6    static InputReader in = new InputReader(System.in);
7    static PrintWriter out = new PrintWriter(System.out);
8
9    public static final int MN = 200020;
10

Problems