通江县城乡建设局门户网站市场营销专业课程

今天学了树状dp和tarjan

树状dp

树状dp，是一种在树形数据结构上应用的动态规划算法。动态规划（DP）通常用于解决最优化问题，通过将问题分解为相对简单的子问题来求解。在树形结构中，由于树具有递归和子结构的特性，因此非常适合应用动态规划来求解。

特点与步骤：

定义状态：首先，需要为树中的每个节点定义一个或多个状态，这些状态通常表示以该节点为根的子树满足某种条件的最优解。

状态转移方程：然后，根据问题的性质，建立状态转移方程。状态转移方程描述了如何由子节点的状态推导出父节点的状态。

遍历树：通常使用深度优先搜索（DFS）来遍历整棵树，并在遍历过程中计算每个节点的状态。遍历的顺序一般是先遍历子节点，再计算父节点的状态，这样可以保证在计算父节点状态时，其子节点的状态已经被计算出来。

Tarjan算法

Tarjan算法是一种用于求解有向图强连通分量的高效算法。强连通分量是指有向图中的一个极大强连通子图，即该子图中的任意两个顶点都互相可达。

核心思想：

Tarjan算法基于深度优先搜索（DFS），利用DFS过程中产生的递归栈和节点的时间戳等信息来判断强连通分量。

关键步骤：

DFS遍历：首先，对有向图进行深度优先搜索。

时间戳记录：为每个节点记录两个时间戳，dfn[u]表示节点u被访问的时间（即DFS序），low[u]表示节点u通过DFS树中的边能回溯到的最早的栈中节点的dfn值。

强连通分量判定：在DFS过程中，如果某个节点u的dfn[u]等于low[u]，则说明以u为根的子树中的所有节点构成了一个强连通分量。