跳转至

基环树

基环树 本质上就是在树上多了一条边。

而 基环树森林 本质上就是在每一颗树上多了一条边

基环树 问题有两种解决思路：

拆边

我们先找到那个环上的一条边，然后将其删去，按照树的方式处理。

最后在把边加上合并

像是这道题：P2607 骑士 - 洛谷

我们先把那多出来的一条边删除，然后以两个点位根跑树上 DP。

重要的是如何合并，我们需要考虑这条边的两个点选货不选的情况，最后合并最大值：

[!success]- CODE

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=4e6+5;
int n;
int cnt;
int c[N];
int f[N][2];
int fa[N];
PII l[N];
int tot,head[N],nxt[N<<1],ver[N<<1];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void add(int a,int b){
  ver[++tot]=b;
  nxt[tot]=head[a],head[a]=tot;
}
int find(int x){
  if(x==fa[x]) return x;
  return fa[x]=find(fa[x]);
}
void dfs(int x,int fa,int t){//表示 to 这个点的骑士不能参见骑士团
  f[x][0]=0;
  if(x==t) f[x][1]=-0x3f3f3f3f;
  else f[x][1]=c[x];
  for(int i=head[x];i;i=nxt[i]){
      int y=ver[i];
      if(y==fa) continue;
      dfs(y,x,t);
      f[x][0]+=max(f[y][0],f[y][1]);
      if(x!=t) f[x][1]+=f[y][0];
  }
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++)
      fa[i]=i;
  for(int i=1;i<=n;i++){
      int a,b;cin>>a>>b;
      c[i]=a;
      int xa=find(i),xb=find(b);
      if(xa==xb)
          l[++cnt]=make_pair(i,b);
      else
          add(i,b),add(b,i);
      fa[xa]=xb;
  }
  int ANS=0;
  for(int i=1;i<=cnt;i++){
      int ans=0;
      dfs(l[i].first,-1,-1);
      ans=f[l[i].first][0];
      dfs(l[i].first,-1,l[i].second);
      ans=max(ans,max(f[l[i].first][0],f[l[i].first][1]));
      ANS+=ans;
  }
  cout<<ANS;
  return 0;
}

留下环

像是下面这个图

屏幕截图 2025-11-13 104140.png

我们把他想象成一个环上挂着很多课树，最后直接合并。