算法竞赛的树和现实生活中的树长得一样，只不过我们习惯于处理问题的时候把树根放到上方来考虑。

这种数据结构看起来像是一个倒挂的树，因此得名。

形式化的定义：

- 有 $n$ 个节点， $n-1$ 条边的连通无向图

- 无向无环连通图

- 任意两个节点之间有且仅有一条简单路径的无向图

## 有关树的定义

### 森林

每个连通分量（连通块）都是树的图

### 生成树

一个图的生成子图，同时要求是树。

### 有根树

指定了一个点是根的树

### 无根树

没有指定一个根节点的树

### 深度

#### 节点的深度

到根节点的距离（最短路径的长度）

#### 树的深度

所有节点的深度的最大值

### 父亲

一个节点到根节点的路径上的第二个节点

### 祖先

一个节点到根节点的路径上，除了它本身外的所有节点

### 子节点

如果 $u$ 是 $v$ 的父亲，那么 $v$ 是 $u$ 的子节点。

### 兄弟

同一个父亲的多个子节点互为兄弟

### 后代（子孙）

子节点和子节点的后代

或者理解成：如果 $u$ 是 $v$ 的祖先，那么 $v$ 是 $u$ 的后代。

### 度数

#### 无根树

和一个点相关的边的个数

#### 有根树

子节点个数

### 叶节点

#### 无根树

度数不超过 $1$ 的节点

??? question " 为什么不是度为 $1$？"
    考虑 $n = 1$ 的时候。

#### 有根树

没有子节点（度数为 $0$）的节点

### 子树

删掉与父亲相连的边后，该节点所在的子图

## 特殊的树

### 只有一个节点

没有边

$n = 1, m = 0$

### 链

点 $i$ 的父亲为 $i - 1$。

树的深度为$n - i$。

### 菊花

所有非根节点的父亲均为根节点。

树的深度为 $1$。

### 二叉树

每个节点最多只有两个儿子（子节点）的树

#### 满二叉树

#### 完全二叉树

这里好像需要有图。（图待补）

## 如何存树

### 存父亲

用一个数组记录每个节点的父亲节点：`fa`数组

### 邻接表

当成图来存

有根树：`vector<int> childs[n], fa[n]`

二叉树：`int lch[n], rch[n], fa[n]`