基环树

ooliver 发布于 2026-06-25 328 次阅读 OI

AI 摘要

基环树是解决“有环的树”问题的关键技巧。从“没有上司的舞会”到“骑士”，当树中多出一条边，如何破环求解？本文带你掌握查找环、断开边、DP求解的完整套路，并实战三个升级版难题。

基环树

P2607 [ZJOI2008] 骑士

没有上司的舞会的加强版，找到基环树的环之后断开一条边，以断边的两个端点为根 dp 即可，注意原图可能是森林。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e6+5;
struct edge{int v,id;};
vector<edge> g[N];
int n,ans,r1,r2,E,a[N],v[N],dp[N][2];

void find(int u,int p){
    v[u]=1;
    for(auto e:g[u]){
        if(e.id==(p^1))continue;
        if(v[e.v]){
            if(!E){r1=u,r2=e.v,E=e.id;}
            continue;
        }
        find(e.v,e.id);
    }
}

void dfs(int u,int p){
    dp[u][0]=0,dp[u][1]=a[u];
    for(auto e:g[u]){
        if(e.id==p||e.id==(p^1)||e.id==E||e.id==(E^1))continue;
        dfs(e.v,e.id);
        dp[u][0]+=max(dp[e.v][0],dp[e.v][1]);
        dp[u][1]+=dp[e.v][0];
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1,w,u,tot=1;i<=n;i++){
        cin>>w>>u;
        a[i]=w;
        g[i].push_back({u,++tot});
        g[u].push_back({i,++tot});
    }
    for(int i=1;i<=n;i++) if(!v[i]){
        E=0;
        find(i,-1);
        dfs(r1,0);int t=dp[r1][0];
        dfs(r2,0);ans+=max(t,dp[r2][0]);
    }
    cout<<ans;
    return 0;
}

P5022 [NOIP 2018 提高组] 旅行 + P5049 [NOIP 2018 提高组] 旅行 加强版

直接按照加强版的数据来做。

对于 $m=n-1$ 的情况，直接将子节点排序再 DFS 即可。

对于 $m=n$，也就是基环树的情况，我们考虑先找出环。当从根节点出发，走到环上。当我们在环上使用回溯时，就相当于断开了当前点到回溯点的那条边、之后就可以按照树的方法来做。考虑贪心在什么情况下回溯：当环上下一个点比回溯后能访问的点要大时，选择回溯。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int n,m,tag,h[N],vis[N],f[N];
vector<int> t[N];

void dfs(int u,int fa){
    cout<<u<<" ";
    for(int v:t[u]) if(v!=fa) dfs(v,u);
}

void dfs1(int u,int fa){
    vis[u]=1,f[u]=fa;
    for(int v:t[u]){
        if(v==fa) continue;
        if(vis[v]){
            if(!tag){
                tag=1,h[v]=1;
                int x=u;
                while(x!=v) h[x]=1,x=f[x];
            }
        }
        else dfs1(v,u);
    }
}

void dfs2(int u,int b){
    vis[u]=1;
    cout<<u<<" ";
    for(int i=0;i<t[u].size();i++){
        int v=t[u][i];
        if(vis[v]) continue;
        int nxt=0;
        for(int j=i+1;j<(int)t[u].size();j++) if(!vis[t[u][j]]){
            nxt=t[u][j];
            break;
        }
        if(h[u]&&h[v]&&!tag){
            if(v>(nxt?nxt:b)){
                tag=1;
                continue;
            }
        }
        dfs2(v,nxt?nxt:b);
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        t[u].push_back(v);
        t[v].push_back(u);
    }
    for(int i=1;i<=n;i++) sort(t[i].begin(),t[i].end());
    if(m==n-1){
        dfs(1,-1);
        return 0;
    }
    dfs1(1,-1);
    tag=0;
    memset(vis,0,sizeof vis);
    dfs2(1,1e9);
    return 0;
}

P4381 [IOI 2008] Island

观察样例，启发我们答案应该是每颗基环树的直径之和，问题转化为怎么求基环树的直径。

基环树的直径应该有两种可能，一种是以环上一点为根的子树的直径、一种是环上取两点的子树深度之和加上两点之间的距离，注意以上提到的子树的每个节点都不在环上。

对于第一种直接套模板就行。对于第二种情况，设环上一点 $u$ 子树深度为 $d_u$，环的前缀和数组为 $dis$，就相当于求 $d_i+d_j+dis_i-dis_j(1\le j<i\le 2len且i-j\le dis)$，其中 $len$ 表示环的长度。对于这个式子，我们整理成 $(d_i+dis_i)+(d_j-dis_j)(1\le j<i\le 2len且i-j\le dis)$，然后对于 $d_j-dis_j$ 套单调队列即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e6+5;
int n,mx,rt,idx,ans,sum;
int vis[N],h[N],dp[N],dis[N<<1],d[N],l[N<<1];
vector<int> r;
struct node{
    int v,w,id;
}f[N];
vector<node> t[N];

void dfs1(int u,int fa){
    vis[u]=1;
    for(node x:t[u]){
        int v=x.v,w=x.w;
        if(x.id==fa) continue;
        if(!vis[v]){
            f[v]={u,w,x.id};
            dfs1(v,x.id);
        }
        else if(!idx){
            vector<int> a;
            int p=u;
            while(p!=v) a.push_back(p),p=f[p].v;
            a.push_back(v);
            reverse(a.begin(),a.end());
            idx=a.size();
            for(int i=0;i<idx;i++) r.push_back(a[i]),h[a[i]]=1;
            for(int i=2;i<=idx;i++) dis[i]=dis[i-1]+f[a[i-1]].w;
            int s=dis[idx]+w;
            for(int i=idx+1;i<=(idx<<1);i++) dis[i]=dis[i-idx]+s;
        }
    }
}

void dfs2(int u,int fa){
    dp[u]=0;
    for(node x:t[u]){
        int v=x.v,w=x.w;
        if(v==fa||h[v]) continue;
        dfs2(v,u);
        mx=max(mx,dp[u]+dp[v]+w);
        dp[u]=max(dp[u],dp[v]+w);
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int v,w;
        cin>>v>>w;
        t[i].push_back({v,w,i});
        t[v].push_back({i,w,i});
    }
    for(int i=1;i<=n;i++) if(!vis[i]){
        r.clear();
        idx=0,sum=0;
        dfs1(i,-1);
        for(int i=0;i<(int)r.size();i++){
            int x=r[i];
            mx=0;
            dfs2(x,-1);
            l[i+1]=l[i+idx+1]=dp[x];
            sum=max(sum,mx);
        }
        deque<node> q;
        for(int i=1;i<=(idx<<1);i++){
            while(q.size()&&i-q.front().w+1>idx) q.pop_front();
            if(q.size()) sum=max(sum,q.front().v+l[i]+dis[i]);
            while(q.size()&&q.back().v<=l[i]-dis[i]) q.pop_back();
            q.push_back({l[i]-dis[i],i,0});
        }
        ans+=sum;
    }
    cout<<ans;
    return 0;
}