基环树学习笔记

大家好，欢迎来到IT知识分享网。

0.前言

只因环树学习笔只因。

如有错误欢迎指出。

1.基本概念

这名字读起来感觉有点矛盾，怎么可能树上面有一个环呢？

比较容易发现，我们也可以把环上的所有边删掉，那么我们就会得到一个森林，再将每个树的答案贡献与环的贡献合并在一起，从而来解决我们基环树的问题。

或者，如果在环上任意拆除一条边，我们就能得到一棵树，也就使得求解树问题的一些思想得以用在它的身上，亦可以成为解决此类问题的关键。

最后，还是把两个基本但个人感觉并不是特别重要的概念粘在下面：

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

2.基环树中如何求环

刚才已经提出了解决基环树问题的两种思路，那么接下来我们面临的问题就是如何判环？这里提供两种思路（本人采用的是后面的一种）

（1）拓扑排序

显然，在排序完之后，如果入度仍然不为0，那么他就一定是环上点。

如果要求具体的顺序的话，可以考虑在环中随便找一个点，直接搜索就可以了。

void topsort() { 
    int l=0,r=0; for(int i=1;i<=n;i++) if(in[i]==1) q[++r]=i; while(l<r) { 
    int now=q[++l]; for (int i=ls[now];i;i=a[i].next) { 
    int y=a[i].to; if(in[y]>1) { 
    in[y]--; if(in[y]==1) q[++r]=y; } } } } 

(2) 搜索

如果当前遇到的点先前搜索过，那么他就肯定在环上，然后可以用一个栈思想，一直弹回去就可以了。

int get_ring(int x,int last)//vis即在不在环上 { 
    if(isring[x]==1) { 
    vis[x]=1,isring[x]=2,ring.push_back(x); return 1; } isring[x]=1; for(int i=fst[x];i;i=arr[i].nxt) { 
    int j=arr[i].tar; if(i==((last-1)^1)+1) continue; if(get_ring(j,i)) { 
    if(isring[x]!=2) { 
    vis[x]=1,isring[x]=2; ring.push_back(x); return 1; } return 0; } } return 0; } 

3.题目中的应用

在题目中就是上述的两种思想的具体应用。

T1 P4381 [IOI2008] Island

题意即给你一颗基环树（不保证联通），让你求这棵树的最大直径。

本体采用上述的第一种思想。

我们将答案分为两种：

• 这条直径不在环上，而是在环上点的一颗子树上，那么这个可以直接用传统的求最长直径的方法。
• 对于另外一种情况，我们可以考虑将其分成三段，一段在一颗子树上，一段在环上，最后一段在另外一颗子树上。形式化的，定义 $d_x$ 表示 $x$ 不经过环上的点能够到达的最远的距离，在环上取两个点 $u,v$，求 $max(d_u+d_v+di{s}_{u,v})$。

可以发现对于两种情况，我们都需要先预处理出 $d$，然后对于情况二，我们用单调队列来维护即可。

#include<bits/stdc++.h> using namespace std; #define maxe  #define maxn  #define int long long struct node { 
    int tar,nxt,num; }arr[maxe*2]; int graphe_cnt,fst[maxn]; void adds(int x,int y,int z) { 
    arr[++graphe_cnt].tar=y,arr[graphe_cnt].nxt=fst[x],fst[x]=graphe_cnt,arr[graphe_cnt].num=z; } int n; int isring[maxn]; bool vis[maxn],has,is[maxn]; vector<int> ring; int sum[maxn*2]; void init() { 
    scanf("%lld",&n); for(int i=1;i<=n;++i) { 
    int x,y; scanf("%lld%lld",&x,&y); adds(i,x,y); adds(x,i,y); } } int get_ring(int x,int last)//判环 { 
    if(isring[x]==1) { 
    is[x]=1; vis[x]=1,isring[x]=2,ring.push_back(x); return 1; } isring[x]=1; for(int i=fst[x];i;i=arr[i].nxt) { 
    int j=arr[i].tar; if(i==((last-1)^1)+1) continue; if(get_ring(j,i)) { 
    if(isring[x]!=2) { 
    vis[x]=1,is[x]=1,isring[x]=2; ring.push_back(x); sum[ring.size()-1]=sum[ring.size()-2]+arr[i].num; return 1; } else sum[0]=arr[i].num; return 0; } } return 0; } int d[maxn],nowans,ans; void dfs(int x,int last)//预处理d { 
    vis[x]=true; for(int i=fst[x];i;i=arr[i].nxt) { 
    int j=arr[i].tar,k=arr[i].num; if(i==((last-1)^1)+1) continue; if(vis[j]) continue; dfs(j,i); nowans=max(nowans,d[x]+d[j]+k); d[x]=max(d[x],d[j]+k); } } void get_d() { 
    for(int i=0;i<ring.size();++i) dfs(ring[i],0); int num=ring.size(); for(int i=0;i<num;++i) { 
    ring.push_back(ring[i]); if(i>1) sum[i+num]=sum[i+num-1]+sum[i]-sum[i-1]; else sum[i+num]=sum[i+num-1]+sum[i]; } } void get_ans()//单调队列 { 
    // cout<<nowans<<endl; deque<int> p; p.push_front(0); for(int i=1;i<ring.size();++i) { 
    while(!p.empty()&&i-p.front()>=ring.size()/2) p.pop_front(); if(p.empty()) { 
    p.push_back(i); continue; } int j=p.front(); // cout<<sum[i]-sum[j]+d[ring[j]]+d[ring[i]]<<endl; nowans=max(sum[i]-sum[j]+d[ring[j]]+d[ring[i]],nowans); while(!p.empty()&&d[ring[p.back()]]+sum[ring.size()-1]-sum[p.back()]<=d[ring[i]]+sum[ring.size()-1]-sum[i]) p.pop_back(); p.push_back(i); } ans+=nowans; } void print_ans() { 
    printf("%lld\n",ans); } void clear() { 
    has=0,nowans=0; ring.clear(); sum[0]=sum[1]=0; } signed main() { 
    init(); for(int i=1;i<=n;++i) { 
    if(vis[i]) continue; // cout<<i<<" yeah!"<<endl; clear(); get_ring(i,0); get_d(); get_ans(); } print_ans(); return 0; } 

T2 Rendezvous

这题同样采用上述的第一种思想。

可以发现，一个基环树除开环以后，会分成多个不同的子树森林。

我们将要求解的两个 $a,b$ 分为以下几种情况进行求解：

• $a,b$ 两者不连通，那么无解，打一个并查集判断即可。
• $a,b$ 在一颗子树上，那么终点就是 $lca(a,b)$，所以答案就是 $(de{p}_a-(de{p}_{lca(a,b)},de{p}_b-de{p}_{lca(a,b)})$。（$dep$ 表示深度，且以上操作可以通过、树上倍增进行维护。）
• 那么显然，剩下的一种情况保证 $a,b$ 所在子树的根节点必然在同一个环上。可以设这两个根节点分别为 $p,q$。显然，我们可以预处理 $p,q$ 两个点的距离 $di{s}_{p,q},di{s}_{q,p}$。那么显然，我们就会得到两种答案，一种是从 $p$ 走到 $q$，一种是从 $q$ 走到 $p$，若是从 $p$ 到 $q$，那么答案为 $(de{p}_a+di{s}_{p,q},de{p}_b)$，反之同理。接着将这些答案通过优先级判断来输出即可。

#include<bits/stdc++.h> using namespace std; #define maxe  #define maxn  struct node { 
    int tar,nxt; }arr[maxe*2]; int graphe_cnt,fst[maxn]; void adds(int x,int y) { 
    arr[++graphe_cnt].tar=y,arr[graphe_cnt].nxt=fst[x],fst[x]=graphe_cnt; } vector<int> g[maxn]; int n,m; int isring[maxn],vis[maxn]; bool used[maxn],has; int times=0,now; vector<int> ring[maxn]; int fa[maxn],in[maxn]; int findroot(int x) { 
    if(fa[x]==x) return x; return fa[x]=findroot(fa[x]); } void unionn(int x,int y) { 
    int p=findroot(x),q=findroot(y); if(p!=q) fa[p]=q; } void init() { 
    scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) fa[i]=i; for(int i=1;i<=n;++i) { 
    int x; scanf("%d",&x); // if(x==i) continue; g[x].push_back(i); adds(i,x); unionn(i,x); in[x]++; } } int get_ring(int x,int last) { 
    if(isring[x]==1) { 
    vis[x]=times,isring[x]=2,ring[times].push_back(x); return 1; } isring[x]=1; for(int i=fst[x];i;i=arr[i].nxt) { 
    int j=arr[i].tar; if(get_ring(j,i)) { 
    if(isring[x]!=2) { 
    vis[x]=times,isring[x]=2; ring[times].push_back(x); return 1; } return 0; } } return 0; } int dp[maxn][21],dep[maxn],num[maxn],belong[maxn]; void dfs(int x,int last)//预处理lca { 
    belong[x]=now; dp[x][0]=last,dep[x]=dep[last]+1; for(int i=1;i<=20;++i) dp[x][i]=dp[dp[x][i-1]][i-1]; for(int i=0;i<g[x].size();++i) { 
    int j=g[x][i]; if(vis[j]==vis[now]) continue; dfs(j,x); } } int lca(int x,int y) { 
    if(dep[x]<dep[y]) swap(x,y); int p=dep[x],q=dep[y]; for(int i=20;i>=0;--i) if(p-(1<<i)>=q) p-=(1<<i),x=dp[x][i]; if(x==y) return x; for(int i=20;i>=0;--i) if(dp[x][i]!=dp[y][i]) x=dp[x][i],y=dp[y][i]; return dp[x][0]; } void prepare() { 
    for(int i=1;i<=n;++i) { 
    int p=findroot(i); if(used[p]) continue; used[p]=1; ++times,has=false; get_ring(i,0); } //处理环上两点距离 for(int i=1;i<=times;++i) for(int j=0;j<ring[i].size();++j) now=ring[i][j],dfs(ring[i][j],0); for(int i=1;i<=times;++i) { 
    for(int j=0;j<ring[i].size();++j) num[ring[i][j]]=j; } } pair<int,int> get_ans(int x,int y)//求解，写的有点小丑。 { 
    int Lca=lca(x,y),p=belong[x],q=belong[y]; if(Lca==x) return make_pair(0,dep[y]-dep[x]); else if(Lca==y) return make_pair(dep[x]-dep[y],0); else if(Lca) return make_pair(dep[x]-dep[Lca],dep[y]-dep[Lca]); else { 
    if(findroot(x)!=findroot(y)) return make_pair(-1,-1); int needx=dep[x]-dep[p],needy=dep[y]-dep[p],need1=num[p]-num[q],need2; // cout<<num[p]<<" "<<num[q]<<" "; if(need1<0) need1+=ring[vis[p]].size(),need2=num[q]-num[p]; else need2=-need1+ring[vis[p]].size(); need1+=needx,need2+=needy; // cout<<need1<<" "<<need2<<endl; if(max(need1,needy)>max(needx,need2)) return make_pair(needx,need2); else if(max(needx,need2)>max(need1,needy)) return make_pair(need1,needy); else { 
    if(min(needx,need2)<min(needy,need1)) return make_pair(needx,need2); else if(min(needx,need2)>min(needy,need1)) return make_pair(need1,needy); else { 
    if(need1>=needy) return make_pair(need1,needy); else return make_pair(needx,need2); } } } } signed main() { 
    init(); prepare(); for(int i=1;i<=m;++i) { 
    int x,y; scanf("%d%d",&x,&y); pair<int,int> ans=get_ans(x,y); printf("%d %d\n",ans.first,ans.second); } return 0; } 

T3 Card Game

一道非常经典但是又极其恶心的综合了树上各大算法的好题。

首先，你得先把图给构造出来。

我们可以将一张卡片的正面与背面建一条边正连向背的单向边。那么显然，要让每一个点的出度都小于等于一才能符合题意，答案即为有向边要反转多少次和方案个数。

对于每个 弱联通块 我们分别进行求解：

• 如果当前连通块边数大于点数，那么显然，所有点的出度之和大于点数，那么根据鸽巢原理，就无法满足条件，所以整个游戏他都无解。
• 如果当前连通块边数小于点数，那么我们可以将这个图转为一棵树，建立无向边，并且若原有图中这条边，那么将其边权设为 $1$，否则设为 $0$。考虑定义 $d{p}_x$ 表示 $x$ 的出度为 $0$ 时，需要修改的边的最小个数是多少。显然我们可以先找一个点作为跟，跑一遍 $dp$ 在进行换根求解。最后要修改的个数即为对所有 $dp$ 取最小值，方案个数即为有多少个 $dp$ 值等于要修改的个数。（$dp$ 转移式就自己想吧，这不是重点）。
• 最后一种情况，及连通块边数等于点数，那么我们同第二种情况建立无向边，转化为无向图后，就可以得到一颗基环树。我们同样采用最开始说的思想一进行求解。首先对于一个环，我们将环上边权为 $1$ 的个数和为 $0$ 的个数求一个最小值即可得到要修改的个数，并且如果两种个数不等，方案就只有一个，否则就是两个。对于除开环的子树，我们对于每个子树的根跑一边 $dp$（不能换根，因为必须满足这个根的出度为0），然后将 $dp$ 与环要修改的个数加起来，就是这种情况的总修改数，并且容易发现，方案数并不会变化。

代码写的有点冗长。

#include<bits/stdc++.h> using namespace std; #define maxe  #define maxn  #define mod  struct node { 
    int tar,nxt; }arr[maxe*2]; int graphe_cnt,fst[maxn]; void adds(int x,int y) { 
    arr[++graphe_cnt].tar=y,arr[graphe_cnt].nxt=fst[x],fst[x]=graphe_cnt; } int n,m; unordered_set<long long> ep; vector<pair<int,int> > g[maxn]; vector<int> ltk[maxn],gg[maxn]; int fa[maxn],cnt[maxn],size[maxn],dp[maxn],cntt[maxn]; bool used[maxn],zz[maxn]; int isring[maxn],sum; bool vis[maxn],has,is[maxn]; int edge,lastans,lastans2=1; vector<int> ring; int findroot(int x) { 
    if(fa[x]==x) return x; return fa[x]=findroot(fa[x]); } void unionn(int x,int y) { 
    int p=findroot(x),q=findroot(y); if(p!=q) fa[p]=q,cnt[q]+=cnt[p],cntt[q]+=cntt[p],size[q]+=size[p]; } void clear() { 
    memset(fst,0,(n+1)*4); memset(cnt,0,(n+1)*4); memset(cntt,0,(n+1)*4); memset(used,0,(n+1)); memset(isring,0,(n+1)*4); memset(vis,0,(n+1)); memset(dp,0,(n+1)*4); memset(is,0,(n+1)); memset(zz,0,(n+1)); graphe_cnt=0,edge=0,lastans=0,lastans2=1; ep.clear(); for(int i=1;i<=n;++i) fa[i]=i,size[i]=1,ltk[i].clear(),g[i].clear(),gg[i].clear(); } char gc(){ 
   static char buf[],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,,stdin),p1==p2)?EOF:*p1++;} template<typename T> void fast_read(T&x){ 
   x=0;bool f=0;static char s=gc();while(s<'0'||s>'9')f|=s=='-',s=gc();while(s>='0'&&s<='9')x=(x<<3)+(x<<1)+(s^48),s=gc();if(f)x=-x;} static char buf[];int len=-1; void flush(){ 
   fwrite(buf,1,len+1,stdout);len=-1;} void pc(const char x){ 
   if(len==)flush();buf[++len]=x;} template<typename T> void fast_write(T x){ 
   if(x<0)x=-x,pc('-');if(x>9)fast_write(x/10);pc(x%10^48);} void input() { 
    fast_read(m); n=2*m; clear(); for(int i=1;i<=m;++i) { 
    int x,y; fast_read(x),fast_read(y); unionn(x,y); is[x]=true,is[y]=true; if(!ep.count(x*ll+y)) cnt[findroot(x)]++; else if(!ep.count(y*ll+x)) swap(x,y),lastans++,lastans2=lastans2*2%mod,cnt[findroot(x)]++; adds(x,y); cntt[findroot(x)]++; ep.insert(x*ll+y); } } int get_ring(int x,int last) { 
    if(isring[x]==1) { 
    vis[x]=1,isring[x]=2,ring.push_back(x); return 1; } isring[x]=1; for(int i=0;i<g[x].size();++i) { 
    int j=g[x][i].first; if(gg[x][i]==last) continue; // cout<<x<<" "<<j<<endl; if(get_ring(j,gg[x][i])) { 
    if(isring[x]!=2) { 
    vis[x]=1,isring[x]=2; ring.push_back(x); sum+=g[x][i].second; return 1; } else sum+=g[x][i].second; return 0; } } return 0; } pair<int,int> solve1(int fa)//点<边 { 
    return make_pair(0,0); } void dfs(int x,int last) { 
    if(zz[x]) return; zz[x]=1; for(int i=0;i<g[x].size();++i) { 
    int j=g[x][i].first; if(last==gg[x][i]||vis[j]) continue; dfs(j,gg[x][i]); dp[x]+=dp[j]+g[x][i].second; } } void get_ans(int x,int last) { 
    if(zz[x]) return; zz[x]=1; for(int i=0;i<g[x].size();++i) { 
    int j=g[x][i].first; if(gg[x][i]==last) continue; if(g[x][i].second) dp[j]=dp[x]-1; else dp[j]=dp[x]+1; get_ans(j,gg[x][i]); } } pair<int,int> solve2(int fa)//点=边 { 
    if(cnt[fa]==1) { 
    if(ltk[fa].size()==1) return make_pair(0,1); // return make_pair(1,max(cntt[fa],1)); } int nowans=0,bj=0; for(int i=0;i<ltk[fa].size();++i) { 
    int j=ltk[fa][i]; for(int k=fst[j];k;k=arr[k].nxt) { 
    g[j].push_back(make_pair(arr[k].tar,1)); g[arr[k].tar].push_back(make_pair(j,0)); gg[j].push_back(++edge); gg[arr[k].tar].push_back(edge); } } sum=0; get_ring(fa,0); nowans+=min(int(ring.size())-sum,sum); if(sum*2==ring.size()) bj=2; else if(ring.size()) bj=1; // cout<<ring.size()<<" "<<sum<<endl; for(int i=0;i<ltk[fa].size();++i) zz[ltk[fa][i]]=0; for(int i=0;i<ring.size();++i) { 
    dfs(ring[i],0); nowans+=dp[ring[i]]; } // cout<<nowans<<endl; ring.clear(); return make_pair(nowans,bj); } pair<int,int> solve3(int fa)//点>边 { 
    if(cnt[fa]==1) { 
    if(cntt[fa]==1) return make_pair(0,1); return make_pair(1,max(cntt[fa],1)); } // cout<<fa<<"-----------"<<endl; for(int i=0;i<ltk[fa].size();++i) { 
    int j=ltk[fa][i]; // cout<<j<<" "; for(int k=fst[j];k;k=arr[k].nxt) { 
    ++edge; g[j].push_back(make_pair(arr[k].tar,1)); g[arr[k].tar].push_back(make_pair(j,0)); gg[j].push_back(edge); gg[arr[k].tar].push_back(edge); } } // cout<<endl; dfs(fa,0); for(int i=0;i<ltk[fa].size();++i) zz[ltk[fa][i]]=0; get_ans(fa,0); int ans=INT_MAX,anss=0; for(int i=0;i<ltk[fa].size();++i) { 
    int j=ltk[fa][i]; if(ans>dp[j]) ans=dp[j],anss=1; else if(ans==dp[j]) anss++; // cout<<dp[j]<<" "; } // puts(""); // cout<<ans<<endl; return make_pair(ans,anss); } pair<int,int> solve() { 
    for(int i=1;i<=n;++i) ltk[findroot(i)].push_back(i); pair<int,int> ans; ans.second=1; for(int i=1;i<=n;++i) { 
    int p=findroot(i); if(!is[i]) continue; if(used[p]) continue; used[p]=true; pair<int,int> now; if(size[p]<cntt[p]) now=solve1(p); else if(size[p]==cnt[p]) now=solve2(p); else now=solve3(p); ans.first+=now.first; ans.second=1ll*ans.second*now.second%mod; } return ans; } signed main() { 
    int T; scanf("%d",&T); while(T--) { 
    clear(); input(); pair<int,int> ans=solve(); if(ans.second==0) puts("-1 -1"); else printf("%d %d\n",ans.first+lastans,int(1ll*ans.second*lastans2%mod)); } return 0; } 

代码略显丑陋。。。

T4 旅行

这个例题主要是写来具体第二种解题思想。

题目其实不难，每次把环上的任意一条边删掉。然后进行搜索求解，最终求得所有解的最大值即可。

#include<bits/stdc++.h> using namespace std; int n,m; int fst[5005],cnt; inline int read() { 
    int flg=1,x=0; char c='\0'; while(!isdigit(c)){ 
   if(c=='-')flg=-1;c=getchar();} while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*flg; } inline void write(int x) { 
    if(x<0) x=-x,putchar('-'); if(x>9) write(x/10); putchar(x%10^48); } pair<int,int> now; struct node { 
    int tar,nxt; }arr[10005]; void adds(int x,int y) { 
    arr[++cnt].tar=y,arr[cnt].nxt=fst[x],fst[x]=cnt; } priority_queue<int> p[5005]; void dfs(int x,int last) { 
    write(x); putchar(' '); for(int i=fst[x];i;i=arr[i].nxt) { 
    int y=arr[i].tar; if(y==last) continue; dfs(y,x); } } int qwq; vector<int> ans[5005],all; bool vis[5005]; void dfs2(int x,int last) { 
    vis[x]=1; ans[qwq].push_back(x); for(int i=fst[x];i;i=arr[i].nxt) { 
    int y=arr[i].tar; if(vis[y]) continue; pair<int,int> no1=make_pair(x,y),no2=make_pair(y,x); if(no1==now||no2==now) continue; dfs2(y,x); } } int main() { 
    n=read(),m=read(); for(int i=1;i<=m;++i) { 
    int x,y; x=read(),y=read(); p[x].push(y),p[y].push(x); } for(int i=1;i<=n;++i) { 
    while(!p[i].empty()) { 
    adds(i,p[i].top()); p[i].pop(); } } if(m<n) { 
    dfs(1,0); } else { 
    for(int i=1;i<=n;++i) { 
    for(int j=fst[i];j;j=arr[j].nxt) { 
    int k=arr[j].tar; if(k<i) continue; now=make_pair(i,k); ++qwq; memset(vis,0,sizeof(vis)); dfs2(1,0); } } for(int i=1;i<=qwq;++i) { 
    // for(int j=0;j<ans[i].size();++j) cout<<ans[i][j]<<" "; // puts(""); if(ans[i].size()<n) continue; bool flg=0; if(!all.size()) { 
    all=ans[i]; continue; } for(int j=0;j<n;++j) { 
    if(all[j]>ans[i][j]) { 
    flg=1; break; } else if(all[j]<ans[i][j]) { 
    break; } } if(flg==true) all=ans[i]; } for(int i=0;i<all.size();++i) { 
    write(all[i]); putchar(' '); } } return 0; } 

4.一些心得

其实看了上面的题解可以发现，基环树其实解题思想并没有那么难，主要是真的很难调。。。

有一个很难处理的地方，就是重边，一般调不出来 99% 都是死在这里了。有些重边会对答案造成影响，所以在搜索时不能传统的去判断，而要写当前遍历到的边是否与上一条边是等效的，所以这里推荐写链式前向星，即下面这行代码：

if(i==((last-1)^1)+1) continue;//i为上一条,j为这一条，且边是从1开始存的 

另外，无向图处理环的时候，记得要把环在想后面复制一份，因为环他有两种行走的方向。

最后，基环树是一种综合性很强的东西，再调他的时候，相信它一定可以增强你的心理承受能力的！

$$\mathcal{T}he\mathcal{E}nd$$