Rare
0/13

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

#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 node    ans = 0 # stores the number of subordinates    for e in edges[x]:        if e != fa[x-1]:            ans += dfs(e)    sub[x-1] = ans # 0-index is more convenient for printing    return ans+1 # add the node x itselfN = int(input())

Problems

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

CSESNormal
Show Tags

Tree, DFS

POINormal
Show Tags

Tree

CCCNormal
Show Tags

Tree, DFS

SilverNormal
Show Tags

Tree, Bipartite

External Sol
CFHard
Show Tags

DFS

POIHard
Show Tags

Tree, Prefix Sums

Wizard's Tour

Try solving this problem on a tree first!

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.