10.4 国庆 环形dp与基环树笔记

1.知识点

环形dp

环形 dp 的概念

• 环形dp与基环树在许多环形结构的问题中，我们可以在环中从某个位置把环断开，把这个环变成线性的，然后进行 \(dp\) 等操作。
• 把能通过上述操作解决的环形问题称作 "可拆解的环形问题" 。

环形 dp 的两种策略

• 第一次在任意位置把环断开成链，按照线性问题求解；第二次通过适当的条件和赋值，保证计算出的状态等价于把断开的位置强制相连。
• 把环断成链，然后复制一倍在末尾

基环树

• \(n\) 个点的树共有 \(n - 1\) 条边，如果再加上一条边，即 \(n\) 个点 \(n\) 条边，那树中必然会出现一个环。
• 把这种 \(n\) 个点 \(n\) 条边的联通无向图，即刚好包含一个环的图，称作 "基环树"。
• 如果不保证连通，那么 \(n\) 个点 \(n\) 条边的无向图也可能是若干棵基环树组成的森林，简称 "基环树森林"。

外向树

• \(n\) 个点 \(n\) 条边，每个点有且仅有 \(1\) 条入边的有向图，被称为 "外向树"。
• \(n\) 个点 \(n\) 条边，每个点有且仅有 \(1\) 条出边的有向图，被称为 "内向树"。

基环树的直径

• 基环树中最长的简单路径被称为基环树的最长链，其长度被称为基环树的直径。

基环树找环

• 自己一个很神奇的方法：

1. 预处理出每个点的 \(father\)
2. 从某个点开始，一直往它的 \(father\) 走，边走边做 \(vis\) 标记，当走到一个已经访问过的节点时，便找到了环。

Code:

int find(int u)//从 u 点开始找环
{
	vis[u] = true;
	node = u;
	while (!vis[fa[node]])
	{
		node = fa[node];
		vis[node] = true;
	}
	return node;
	//node 为环的一点
}

T1

Link

• \(n\) 个点，\(m\) 条边。每次从任意一个点出发，每次可以走向一个没有访问过的点，或者沿着第一次访问这个点时经过的边后退到上一个点。
• 每到达一个点时，把这个点的编号记录下来，这样最后会组成一个长度为 \(n\) 的序列，期望这个序列的字典序最小，求出这个序列。
• 对于 \(60\%\) 的数据，满足 \(n \leq 5000\), \(m = n - 1\)。
• 对于 \(40\%\) 的数据，满足 \(n \leq 5000\)，\(m = n\)。

Solution

• 数据范围提示了做法 /kk。
• \(60 pts\) 就是白送的，容易可以发现一个性质：到达一个点时，一定要遍历完它的子树后才能返回。
• 题目要求字典序最小，于是用 \(vector\) 存图，对每个点的子树内进行排序，最后直接 \(dfs\) 即可。
• 而对于另外的 \(40 pts\)，因为 \(m = n\)，所以这是一棵基环树。
• 手玩一下基环树的样例可以发现，一定有一条边是无法经过的，我们枚举这条边，然后 \(dfs\) 即可。
• ps：加强版无法通过，可能是 \(vector\) 常数太大了/bx/bx。