基环树

一、基本概念

如果一张无向连通图包含恰好一个环，则称它是一棵基环树(Pseudotree)。

如果一张有向弱连通图每个点的入度都为 ，则称它是一棵 基环外向树。

如果一张有向弱连通图每个点的出度都为 ，则称它是一棵 基环内向树。

多棵树可以组成一个森林(Forest) ，多棵基环树可以组成基环森林(Pseudoforest) ，多棵基环外向树可以组成基环外向树森林，多棵基环内向树可以组成基环内向森林(Functional graph) 。

二、算法实现

在基环树中，有许多独一无二的性质，这也就成为良心出题人增加题目难度的一种措施。通常会结合树的直径进行考察。

下面就一些例题进行分析

下面以 [IOI2008] Island 举例。

题目大意：现有一个基环森林，求出森林中每颗基环树的直径的和。

基环树直径，就是图中最长链的长度。因为基环树的一些特性，这也成为常考点。 显然，基环树的最长链可能有两种情况：

  • 在去掉“环”的某棵子树中。

  • 经过“环”，其两端分别在去掉“环”上所有边之后的两颗不同子树中。

我们可以先用一次dfs找出基环树中的“环”，把“环”上的节点做标记，并用数组 ring[] 记录。设环上的节点为 \(s_1,s_2,\cdots,s_t\)。

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
bool dfs(int x,int last){//用bool数组进行记录：true表示在环上；false表示不在环上
    if(temp[x]==1){//如果这个点被访问过，说明是环的衔接点，记录，停止深入搜索
        temp[x]=2;
        ring[++cnt]=x;
        c[x]=1;//标记这个点已访问
        return 1;
    }
    temp[x]=1;//标记这个点
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(i!=(last^1)&&dfs(y,i)){
            if(temp[x]!=2){//如果这个点不是环的衔接点
                c[x]=1;
                ring[++cnt]=x;
                s[cnt]=s[cnt-1]+edge[i];//前缀和记录（后面会提到）
            }
            else{//如果这个点是环的衔接点
                s[start-1]=s[start]-edge[i];
                return 0;
            }
            return 1;
        }
    }
    return 0;
}

从每个 \(s_i\) 出发，在不经过环上其他节点的前提下，再次执行dfs，即可访问去掉“环”之后以 \(s_i\) 为根的子树。在这样的每棵子树中，按照求树的直径的方法进行树形DP并更新答案，即可处理第一种情况。同时，还可以计算出 \(d[s_i]\)，表示从节点 \(s_i\) 出发走向以 \(s_i\) 为根的子树，能够到达的最远节点距离。

1
2
3
4
5
6
7
8
9
10
void tree_dp(int x){//树形DP
    c[x]=1;//标记这个点已访问
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(c[y]) continue;
        tree_dp(y);
        treeans=max(treeans,d[x]+d[y]+edge[i]);
        d[x]=max(d[x],d[y]+edge[i]);
    }
}

最后，考虑第二种情况。这相当于找到环上两个不同的节点 \(s_i,s_j\)，使得 \(d[s_i]+d[s_j]+dist(s_i,s_j)\) 最大。其中，\(dist(s_i,s_j)\) 表示 \(s_i,s_j\) 在环上的距离，有顺时针、逆时针两种走法，取较长的一种。可以将环断开成链再复制一倍，再用单调队列解决。（还可以用前缀和的方法快速求出，下面会提及）。

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
ll slove(int x){
    start=cnt+1;//因为这是一张基环森林，所以要记录入点下标
    ll ans_1=0;
    dfs(x,0);//找环上的点
    for(int i=start;i<=cnt;i++){
        treeans=0;
        tree_dp(ring[i]);//对每一个树进行树形DP，找到树上直径
        ans_1=max(ans_1,treeans);//记录最大直径
    }
    ll ans_2=0;
    for(int i=start;i<=cnt;i++){//复制环
        dp[i+cnt-start+1]=dp[i]=d[ring[i]];
        s[i+cnt-start+1]=s[i+cnt-start]+s[i]-s[i-1];
    }
    deque<int> q;
    for(int i=start;i<=2*cnt-start+1;i++){
        while(q.size()&&q.front()<=i-cnt+start-1){//优先队列，先清除不在区域范围内的点
            q.pop_front();
        }
        if(q.size()){//如果队列里还有点，进行记录
            ans_2=max(ans_2,dp[i]+dp[q.front()]+s[i]-s[q.front()]);
        }
        while(q.size()&&dp[q.back()]-s[q.back()]<=dp[i]-s[i]){//清除比这个点小的点
            q.pop_back();
        }
        q.push_back(i);//插入
    }
    return max(ans_1,ans_2);//取最大值
}

如果需要，可以打开完整的代码