浅谈基环树

浅谈基环树

定义

对于一个连通图图 \(G\)，如果其点数与边数相等，那我们便称它为一个基环树。
也就是说，在一棵树上加一条边，就形成了一棵基环树。
一般地，如果图 \(G\) 不连通，其点数与边数相等，那么肯定就是若干个基环树的组合，称之为基环森林。
我们通常将基环树分为以下几类：

• 无向基环树：基环树由无向边连接。
  
  
  
  
• 内向基环树：基环树由有向边连接，每个节点出度都为 \(1\)。
  
  
  
  
• 外向基环树：基环树由有向边连接，每个节点入度都为 \(1\)。
  
  
  
  

不同的基环树，我们都有不同的处理方法，选对处理方法往往能够事半功倍，具体会在下面例题中讲到。
思路

对于一棵基环树的问题，我们通常有以下两种处理方法：

• 我们将一棵基环树视为一个环上面挂了很多子树，然后分别处理每一个子树，将信息合并到在环上的根上，把一棵基环树问题转化为一个在环上的问题
  
  
  
  
• 我们将一棵基环树视为一个多了一条边的树，可以先将这一边删掉，将其转化为树上问题，之后我们再考虑加上这条边造成的影响，将之前的结果加上影响即可
  
  
  
  

例题

P2607 [ZJOI2008] 骑士 link

题目大意

给出一个 \(n\)（\(1 \le n \le 10^6\)）个点的带点权的基环森林，求这个基环森林的最优独立集。
最优独立集：选出若干个点，使其两两之间没有连边，最大化这些点的点权和。
解题思路

我们将一个骑士和他痛恨的骑士连边，由于两者间只要选一个另一个就不能选，所以可以连无向边，因此这就构成了一个无向基环森林。
对于每一棵基环树，我们都求出它的最优独立集，最后相加即可。
现在我们先考虑思路 2。
首先，我们需要找到这棵基环树的环，将其上的一条边断掉，也就是说只需要求环上的一条边即可。
无向基环树找环需任选一点为根，进行 dfs，访问过的点都进行标记，直到经过一条边到达的点已经标记过，就说明这条边在环上，记录即可。
代码实现上有很多点要注意，由于存在二元环的情况，即父子之间成环，也就是说父子之间有两条边，我们删除环上一条边后，仍然可以通过第二条边到达父亲。
这说明我们不能使用点判断是否重复走，也就是不能使用 v != fa[v]，因为这样会导致 v 不能通过另一条边到达 fa[v]，所以需要通过边来判断，即走的这条边是否和上一条边相同。
具体地，我们使用链式向前星加边时对应双向边的编号是相邻的，这样我们就令编号从 \(2\) 开始，使得边 i 的对应边即为 i ^ 1，再在 dfs 时记录上一次经过的边 pre，通过 (i ^ 1) != pre 判断是否经过是否经过上一次经过的边。（如果链式向前星一开始初始化为 \(0\) 就不能让编号从 \(0\) 开始，因为 \(0\) 号会被认为是没有边）
同理，在之后的 dp 中，我们判断是否经过删除的那条边时也不能用点判断，要记录删除的边的编号通过边判断。
这样，记录了删除的边之后，确保每次不经过这条边，便可以开始树形 dp：

• 状态表示：\(dp_{i,0/1}\) 表示以 \(i\) 为根的子树内，不选/选 \(i\) 号节点，其最大独立集的大小。
  
• 初始化：\(dp_{i,0} = 0\)，\(dp_{i,1} = a_i\)（\(a_i\) 为 \(i\) 的权值）
  
• 状态转移
  
  
  
  • 不选 \(i\)：则儿子无限制，即
    \[dp_{i,0} = \sum{\max(dp_{son,1},dp_{son,0})}\]
    
  • 选 \(i\)：则儿子都不能选，即
    \[dp_{i,1} = \sum{dp_{son,0}}\]
    
  
  
• 答案：\(\max(dp_{root, 0},dp_{root, 1})\)
  

最后考虑删除的边 \((u, v)\) 造成的影响。
删除后，有可能两者都选，不符合题意，因此我们要使其最多只选一个。
可以先钦定 \(u\) 不选，以 \(u\) 为根跑一遍 dp，再钦定 \(v\) 不选，以 \(v\) 为根跑一遍 dp，这使得至少有一个不选，最后我们合并两者的答案，\(\max(dp_{u, 0}, dp_{v, 0})\) 即为答案。
另外，本题也可以使用思路 1，将每个子树 dp 后再在环上 dp，但很显然其实现难度大于思路 2，故不再赘述。
代码实现

[code]#include #define endl "\n"#define ll long longusing namespace std;const int N = 1e6 + 10;struct edge{        int to, next;} e[N > n;        for (int i = 1; i > a >> v;                add(i, v);                add(v, i);        }        for (int i = 1; i  w;                add(i, v, w);                add(v, i, w);        }        for (int i = 1; i > w;                deg[fa]++;        }        topo();        for (int i = 1; i  p;                deg[p]++;        }        for (int i = 1; i