### You're not signed in!

Sign in to save your progress and sync your settings across devices.

# Introduction to Tree Algorithms

Authors: Nathan Chen, Siyong Huang

### Prerequisites

Introducing a special type of graph: trees.

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

- If the tree is rooted, the
- 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
- 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;34const int SZ = 2e5;56vector<int> children[SZ];7int subtree_size[SZ], depth[SZ];89void 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.*;34public class Subordinates5{6 static InputReader in = new InputReader(System.in);7 static PrintWriter out = new PrintWriter(System.out);89 public static final int MN = 200020;10

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

CF | Very Easy | ## Show TagsTree, DFS | Check CF | ||

CF | Easy | ## Show TagsTree, DFS | Check CF | ||

Silver | Easy | ## Show TagsDFS | External Sol | ||

IOI | Easy | ||||

CSES | Normal | ## Show TagsTree, DFS | CPH 14.2 | ||

CSES | Normal | ## Show TagsTree, DFS | CPH 14.2 | ||

CSES | Normal | ## Show TagsTree, DFS | View Solution | ||

CCC | Normal | ## Show TagsTree, DFS | |||

Silver | Normal | External Sol | |||

CF | Hard | ## Show TagsDFS |

### Wizard's Tour

Try solving this problem on a tree first!