学习笔记 - 树上常用算法

一、树的定义、表示

  • 定义：连通且无环的无向图。

  • 等价条件：

1.$\ $连通，且含有 $n$ 个点、$n-1$ 条边。
2.$\ $任意两点间恰有一条路径。
3.$\ $无向无环的连通图。

1.1.1 无根树

  • 满足上述定义、没有其他限制。
  • 每个节点的地位是相同的。
  • 如上图。

1.1.2 有根树

  • 在定义的基础上、指定一个节点为“根”。
  • 相比无根树，有根树更多地利用树的性质，组织结构更加清晰。
  • 树上的问题一般先转化成有根树再解决。

1.2 树结构的特点

  • 树是具有递归结构的。
  • 一个节点即是一棵树，若根节点为 $a$ 节点，其任意一个孩子节点 $b$，与所有不用通过 $a$ 节点即可和 $b$ 相连的节点也构成一棵树，称为以 $b$ 为根的 $a$ 的一棵子树，$b$ 的任意一棵子树也是 $a$ 的一棵子树。
  • 如果一棵树是有根的，那么某个节点 $a$ 的深度 $d(a)= d(father(a))+1$,其中 $father(a)$ 为 $a$ 的父亲节点，另 $d(root)=1$。

1.3 有根树的存储

  • 方法一：
    除了根没有父亲，所有节点都有唯一的父亲。
    记录每个节点的父节点即可。
    缺点：不能从根开始遍历整棵树
    应用：并查集

  • 方法二：
    用邻接表存储 (同普通的无向图)。
    应用：(很多 OI 题中) 只知道树边的两个端点、不知道父子关系的情况，任选一个点为根。

树的表示和存储-邻接表

  • 实现一：
  • 实现二：

二、树的遍历

  • 深度优先 - DFS
    最常用的遍历方式，遍历一个结点后接下来遍历这个结点的第一个没有被遍历过的子节点，如果没有这样的点就退出，时间复杂度 $O(n)$。(先序、中序、后序)

    过去：已经访问
    现在：正在访问
    将来：未访问

  • 广度优先 - BFS
    树上的广度优先遍历实质上是对树上的所有结点按照到根结点的距离进行分层进入队列依次处理，时间复杂度 $O(n)$。

习题：

思路：

  • HDU2376 树上平均距离

三、树型动态规划

  • 树型动态规划就是在“树形”数据结构上进行动态规划，一般的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法(顺推、逆推)，而树型动态规划是建立在树上的，所以也相应的有二个方向：

1.$\ $ 叶→根:即根的子节点传递有用的信息给根，之后由根得出最优解的过程。
2.$\ $ 根→叶:通常我们可以先任选某顶点dfs遍历一遍树，再用二次扫描换根的方式将信息传递到所有节点，过程中利用每条边来父子交换转移信息。

3.1 特点：

1.$\ $ 一般按照后序遍历的顺序，即处理完儿子再处理当前节点这符合树的子结构的性质。
2.$\ $ 实现方式:树形 DP 是通过记忆化搜索实现的，因此采用的是递归方式。
3.$\ $ 时间复杂度:树形 DP 复杂度基本上是 $O(n)$;若有附加维 $m$ 则是 $O(n*m)$

3.2 动态规划算法必须满足的条件

1.$\ $ 阶段性。 整个问题的求解可以划分为若干个阶段的一系列决策过程（与树的层次性相对应）。
2.$\ $ 最优子结构性质。 一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的（与树的递归结构相对应)。
3.$\ $ 无后效性。 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态它以前各阶段的状态无法直接影响它未来的决策，换句话说，每个状态都是过去历史的一个完整总结（与 dfs 的时间戳特点相对应）。

3.3 经典问题:树的独立集、支配集

  • 对于一棵有 $N$ 个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻(称为最大独立集)。
  • 对于最大独立集，每个点也只有两种状态,即属于点i属于独立集或者不属于独立集两种情况，通常我们可以设状态:

1.$\ $ $dp[i][0]$ 表示点 $i$ 属于独立集的情况下，最大独立集中点的个数。
2.$\ $ $dp[i][1]$ 表示点i不属于独立集的情况下，最大独立集中点的个数。

习题:

思路：
每个节点给定一个值，子节点和父亲节点不能同时选取，求能够选取的最大价值。

持续更新中。。。