# 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 | ||

SecondThread |

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++

#include <bits/stdc++.h>using namespace std;const int SZ = 2e5;vector<int> children[SZ];int subtree_size[SZ], depth[SZ];void dfs_size(int node) {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.

import java.io.*;import java.util.*;public class Subordinates{static InputReader in = new InputReader(System.in);static PrintWriter out = new PrintWriter(System.out);public static final int MN = 200020;

Python

In the Python solution, we need to set recursion limit to $2\times10^5$.

import syssys.setrecursionlimit(200006) # set recursion limitdef dfs(x): # x is the current nodeans = 0 # stores the number of subordinatesfor e in edges[x]:if e != fa[x-1]:ans += dfs(e)sub[x-1] = ans # 0-index is more convenient for printingreturn ans+1 # add the node x itselfN = int(input())

## Problems

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

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 | ||||

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

POI | Normal | ## Show TagsTree | ||||

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

Silver | Normal | ## Show TagsTree, Bipartite | External Sol | |||

CF | Hard | ## Show TagsDFS | ||||

POI | Hard | ## Show TagsTree, Prefix Sums |

### Wizard's Tour

Try solving this problem on a tree first!

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

## Give Us Feedback on Introduction to Tree Algorithms!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.