之前的 DP 都是在线性结构上进行的，实际上 DP 还可以在树上或者 DAG 上进行。本文将对这些内容进行简单的介绍。

在无向图中，生成树指一棵由全部顶点和组成的树，而当中边权之和最小的生成树称为最小生成树（Minimum Spanning Tree，MST）。本文会引导你学习 MST 的 Kruskal 和 Prim 算法。

在图中，如何判断一张图是否连通？如果删掉某条边，它还连通吗？有向图呢？这些操作有什么特殊性质吗？本文将探讨以 Tarjan 算法为核心的有关图的连通性的问题和欧拉路问题。

进入 NOIP 计划后期，开始针对性地刷一些 CF 题。

概率论研究的是随机事件，本文将简单介绍概率论。

线性代数是代数学的一个分支，主要处理线性关系问题。OI 中用到的相关知识并不多，主要是矩阵乘法与高斯消元等，本文将简单介绍这些内容。

在 NOIP 范围内需要掌握的较难 DP 包括：状压 DP、单调队列优化 DP 和倍增优化 DP。

本文对简单的树形问题进行了讲解。

最短路是图论中的常考问题，本文引导你学习最短路的 Floyd，BellmanFord 及 Djikstra 算法，以及它们的各种应用。还有一种基于最短路的系统：差分约束系统。

区间 DP 是线性 DP 的一种特殊形式，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。高维 DP 则是线性 DP 的扩展，大部分是从一条链扩展为了二维结构。