基环树一统天下千秋万代

概述基环树，又称环套树，顾名思义，为树上多一条边，\(n\)个节点\(n\)条边。 \(First\)无论啥题，你基环树总得找环，不找环你玩啥呢…… 我找到了三种方法找环，各有千秋，注释中有，就直接放上来了 //https://www.cnblogs.com/akura/p/10838613.html#include<bits/stdc++.h>using namespace std;inlin

基环树，又称环套树，顾名思义，为树上多一条边，\(n\)个节点\(n\)条边。

\(First\)无论啥题，你基环树总得找环，不找环你玩啥呢……

我找到了三种方法找环，各有千秋，注释中有，就直接放上来了

//https://www.cnblogs.com/akura/p/10838613.HTML#include<bits/stdc++.h>using namespace std;inline int read(){    int f=1,w=0;char x=0;    while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}    while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}    return w*f;}const int N=200010;int n,num_edge,Cnt,top,Time;int head[N<<2],Cir[N],Dag[N],boki[N],Vis[N];struct Edge{int next,to,dis;} edge[N<<2];inline voID Add(int from,int to,int dis){    edge[++num_edge].next=head[from];    edge[num_edge].dis=dis;    edge[num_edge].to=to;    head[from]=num_edge;}inline voID Bfs_Find_Cir()//Bfs找环还是少用，它忽略了原本的树形结构，仅能找到环上的点（或者说环边不太好找）{    queue<int> q;    for(int i=1;i<=n;i++) if(Dag[i]==1) q.push(i);    while(!q.empty())    {        int x=q.front();q.pop();        for(int i=head[x];i;i=edge[i].next)        {            Dag[edge[i].to]--;            if(Dag[edge[i].to]==1) q.push(i);        }    }    for(int i=1;i<=n;i++) if(Dag[i]==2) Cir[++Cnt]=i,boki[i]=1;}int Ink[N],Stk[N];inline voID Dfs_For_Cir_Stk(int pos,int fth)//这是用栈实现的Dfs，但是重点是d出 *** 作，避免将非环点放入(针对有向图){    Vis[pos]=1,Stk[++top]=pos;Ink[pos]=1;    for(int i=head[pos];i;i=edge[i].next)        if(edge[i].to!=fth)            if(Vis[edge[i].to])            {                if(Ink[edge[i].to])                {                    for(int Now=Stk[top];Now!=edge[i].to;Now=Stk[--top])                        Cir[++Cnt]=Now,Ink[Now]=0;                    Cir[++Cnt]=edge[i].to;                }            }            else Dfs_For_Cir_Stk(edge[i].to,pos);    Ink[pos]=0,--top;}int Dfn[N],fa[N];inline voID Dfs_For_Cir_Dfn(int pos,int fth)//这是用时间戳实现的Dfs（个人感觉这个更好一些，重点是用Dfn防止找两遍）{    Dfn[pos]=++Time;fa[pos]=fth;    for(int i=head[pos];i;i=edge[i].next)        if(edge[i].to!=fth)            if(Dfn[edge[i].to])            {                if(Dfn[edge[i].to]>Dfn[pos])                {                    for(int Now=edge[i].to;Now!=pos;Now=fa[Now])                        Cir[++Cnt]=Now;                    Cir[++Cnt]=pos;                }            }            else Dfs_For_Cir_Dfn(edge[i].to,pos);}int main(){#ifndef ONliNE_JUDGE    freopen("A.in","r",stdin);    //freopen("B.in",stdin);#endif    n=read();    for(int i=1,u,v,d;i<=n;i++)    {        u=read(),v=read(),d=read();        Add(u,d),Add(v,d);Dag[v]++,Dag[u]++;    }    Bfs_Find_Cir(); for(int i=1;i<=Cnt;i++) printf("%d",Cir[i]);}

例题：\(IOI2008Island\)

思路很好想，找环，断环为链，单调队列维护最大值。

实现细节有点繁琐，还有一个双倍经验（\(IOI\)的是基环树森林，此题是基环树）

#include<bits/stdc++.h>using namespace std;#define int long longinline int read(){    int f=1,w=0;char x=0;    while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}    while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}    return w*f;}const int N=1000010;int Max1,Max2,Cnt;int num_edge,n,Tim,ans;pair<int,int> Cir[N<<1];int head[N<<1],Dep[N],Used[N];int Vis[N],ID[N],fa[N],Dfn[N],Sum[N<<1];struct Edge{int next,dis;} edge[N<<1];inline int C(int i) {return Cir[i].first;}inline voID Add(int from,int dis){    edge[++num_edge].next=head[from];    edge[num_edge].dis=dis;    edge[num_edge].to=to;    head[from]=num_edge;}inline voID Dfs_For_Cir_Dfn(int pos,int fth,int lID){    Dfn[pos]=++Tim,fa[pos]=fth,ID[pos]=lID;    for(int i=head[pos];i&&!Cnt;i=edge[i].next)        if(edge[i].to!=fth)        {            if(Dfn[edge[i].to])            {                if(Dfn[edge[i].to]>Dfn[pos])                {                    for(int Now=edge[i].to;Now!=pos;Now=fa[Now])                        Cir[++Cnt]=make_pair(Now,edge[ID[Now]].dis),Vis[Now]=1;                    Cir[++Cnt]=make_pair(pos,edge[i].dis),Vis[pos]=1;return ;                }            }            else Dfs_For_Cir_Dfn(edge[i].to,pos,i);        }}inline voID Dfs_For_Dep(int pos,int fth){    Used[pos]=1;    for(int i=head[pos];i;i=edge[i].next)        if(edge[i].to!=fth&&!Vis[edge[i].to])        {            Dfs_For_Dep(edge[i].to,pos);            Max1=max(Max1,Dep[pos]+Dep[edge[i].to]+edge[i].dis);            Dep[pos]=max(Dep[pos],Dep[edge[i].to]+edge[i].dis);        }}main(){#ifndef ONliNE_JUDGE    freopen("A.in",x,d;i<=n;i++)        x=read(),d=read(),Add(i,Add(x,i,d);    for(int i=1;i<=n;i++)        if(!Used[i])        {            deque<int> q;Max1=Max2=0;            Cnt=0;Dfs_For_Cir_Dfn(i,0);            for(int j=1;j<=Cnt;j++) Dfs_For_Dep(Cir[j].first,0),Cir[j+Cnt]=Cir[j];            /*有点奇怪的前缀和*/            for(int j=1;j<=(Cnt<<1);j++) Sum[j]=Sum[j-1]+Cir[j-1].second;            /*单调队列出一定要注意在队中的到底是什么*/            for(int j=1;j<=(Cnt<<1);j++)            {                while(q.size()&&(j-q.front())>=Cnt) q.pop_front();                if(q.size()) Max2=max(Max2,Dep[C(j)]+Dep[C(q.front())]+Sum[j]-Sum[q.front()]);                while(q.size()&&Dep[C(q.back())]-Sum[q.back()]<=Dep[C(j)]-Sum[j]) q.pop_back();                q.push_back(j);            }            ans+=max(Max1,Max2);        }    printf("%lld",ans);}

例题：\(NOI2012\)迷失游乐园

换根\(DP+\)基环树，思路不难，要考虑的东西很多，因为我直接在环上跑编号，所以细节更多。。。

一篇很清晰的题解

#include<bits/stdc++.h>using namespace std;inline int read(){    int f=1,w=0;char x=0;    while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}    while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}    return w*f;}const int N=100010,M=30;pair<int,int> Cir[N];int num_edge,m,Cnt;int ID[N],Nex[N],Tag[N];double Up[N],Down[N],ans[N],dis[M][M],Ans;int head[N<<1],Son[N],Vis[N],fa[N];struct Edge{int next,dis;} edge[N<<1];inline voID Add(int from,int dis){    edge[++num_edge].next=head[from];    edge[num_edge].dis=dis;    edge[num_edge].to=to;    head[from]=num_edge;}inline voID Dfs_For_Tree_Down(int pos,int fth){    for(int i=head[pos];i;i=edge[i].next)        if(edge[i].to!=fth&&!Vis[edge[i].to])            Dfs_For_Tree_Down(edge[i].to,pos),Son[pos]++;    for(int i=head[pos];i;i=edge[i].next)        if(edge[i].to!=fth&&!Vis[edge[i].to])            Down[pos]+=Down[edge[i].to]+edge[i].dis*1.0;    if(Son[pos]) Down[pos]=Down[pos]/(Son[pos]*1.0);}inline voID Dfs_For_Tree_Up(int pos,double dis){    if(m==n-1)    {        if(Son[fth]&&fth!=1)            Up[pos]=(Up[fth]+Down[fth]*Son[fth]-Down[pos]-dis)/Son[fth]+dis;        else if(fth==1&&Son[fth]>1)            Up[pos]=(Up[fth]+Down[fth]*Son[fth]-Down[pos]-dis)/(Son[fth]-1)+dis;        else if(fth==1&&Son[fth]==1) Up[pos]=dis;        if(pos!=1) ans[pos]=(Down[pos]*Son[pos]+Up[pos])/(Son[pos]+1);        else ans[pos]=Down[pos];    }    else    {        if(Son[fth]&&!Vis[fth])            Up[pos]=(Up[fth]+Down[fth]*Son[fth]-Down[pos]-dis)/Son[fth]+dis;        else if(Vis[fth])            Up[pos]=(Up[fth]*2+Down[fth]*Son[fth]-Down[pos]-dis)/(Son[fth]+1)+dis;        ans[pos]=(Up[pos]+Down[pos]*Son[pos])/(1+Son[pos]);    }    for(int i=head[pos];i;i=edge[i].next)        if(edge[i].to!=fth&&!Vis[edge[i].to])           Dfs_For_Tree_Up(edge[i].to,edge[i].dis*1.0);}inline voID Find_Dia(int pos,int lID){    Dfn[pos]=++Tim;fa[pos]=fth,ID[pos]=lID;    for(int i=head[pos];i&&!Cnt;i=edge[i].next)        if(edge[i].to!=fth)        {            if(Dfn[edge[i].to])            {                if(Dfn[edge[i].to]>Dfn[pos])                {                    for(int Now=edge[i].to;Now!=pos;Now=fa[Now])                    {                        Cir[++Cnt]=make_pair(Now,edge[ID[Now]].dis);                        Vis[Now]=1,Tag[Now]=Cnt;                    }                    Cir[++Cnt]=make_pair(pos,edge[i].dis);                    Vis[pos]=1,Tag[pos]=Cnt;                }            }else Find_Dia(edge[i].to,i);        }}inline voID Work(int Root){    Find_Dia(Root,0);    for(int i=1;i<=Cnt;i++) Dfs_For_Tree_Down(Cir[i].first,0);    for(int i=1;i<=Cnt;i++)    {        if(i!=1) dis[i-1][i]=dis[i][i-1]=Cir[i-1].second*1.0;        if(i!=Cnt) dis[i][i+1]=dis[i+1][i]=Cir[i].second*1.0;    }    dis[1][Cnt]=dis[Cnt][1]=Cir[Cnt].second*1.0;    for(int i=1;i<=Cnt;i++)    {        int Now=Cir[i].first;double P=1.0;        for(int j=i+1;j!=i;j++)        {            if(j>Cnt) j-=Cnt;if(j==i) break;            int Pos=Cir[j].first;int w=dis[j][!(j-1)?Cnt:j-1];            if(j==(!(i-1)?Cnt:i-1)) Up[Now]+=P*(w+Down[Pos]);            else Up[Now]+=P*(w*1.0+Down[Pos]*Son[Pos]/(Son[Pos]+1)*1.0);            P/=Son[Pos]+1;        }        P=1.0;        for(int j=i-1;j!=i;j--)        {            if(j<=0) j+=Cnt;if(j==i) break;            int Pos=Cir[j].first;int w=dis[j][(j+1)>Cnt?1:j+1];            if(j==((i+1)>Cnt?1:i+1)) Up[Now]+=P*(w+Down[Pos]);            else Up[Now]+=P*(w*1.0+Down[Pos]*Son[Pos]/(Son[Pos]+1)*1.0);            P/=Son[Pos]+1;        }        Up[Now]/=2;    }    for(int i=1;i<=Cnt;i++)        for(int j=head[Cir[i].first];j;j=edge[j].next)            if(!Vis[edge[j].to])                Dfs_For_Tree_Up(edge[j].to,Cir[i].first,edge[j].dis);    for(int i=1;i<=Cnt;i++)    {        int pos=Cir[i].first;        ans[pos]=(Up[pos]*2+Down[pos]*Son[pos])/(2+Son[pos]);    }}int main(){#ifndef ONliNE_JUDGE    freopen("A.in",stdin);#endif    n=read(),m=read();    for(int i=1,d;i<=m;i++)        u=read(),Add(u,d);    if(m==n) Work(1);    else Dfs_For_Tree_Down(1,Dfs_For_Tree_Up(1,0);    for(int i=1;i<=n;i++) Ans+=ans[i];printf("%.5lf",Ans/n*1.0);}

这是个半成品，后面会补锅（也可能咕咕咕） 总结

以上是内存溢出为你收集整理的基环树一统天下千秋万代全部内容，希望文章能够帮你解决基环树一统天下千秋万代所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。