Rare
0/11

# Introduction to Tree Algorithms

Authors: Nathan Chen, Siyong Huang

### Prerequisites

Introducing a special type of graph: trees.

ResourcesSolution - SubordinatesProblems
Edit on Github

Focus Problem – read through this problem before continuing!

Trees are generally treated very differently from general graph problems.

## Resources

Resources
CPH traversing tree, diameter

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.

C++

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

Java

### Warning!

Because Java is so slow, an adjacency list using lists/arraylists results in TLE. Instead, the Java sample code will use the Chinese edge representation.

1import java.io.*;2import java.util.*;3
4public class Subordinates5{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

StatusSourceProblem NameDifficultyTagsSolution
CFVery Easy
Show Tags

Tree, DFS

Check CF
CFEasy
Show Tags

Tree, DFS

Check CF
SilverEasy
Show Tags

DFS

External Sol
IOIEasy
CSESNormal
Show Tags

Tree, DFS

CPH 14.2
CSESNormal
Show Tags

Tree, DFS

CPH 14.2
CSESNormal
Show Tags

Tree, DFS

View Solution
CCCNormal
Show Tags

Tree, DFS

SilverNormalExternal Sol
CFHard
Show Tags

DFS

### Wizard's Tour

Try solving this problem on a tree first!