前言：怎么感觉基环树好像不是NOIP的知识点？（之前都没学过耶！
尽管如此，今天还是来学了学基环树。（开始复习！
一.概念：
其实基环树也没有多难，也就比普通的树多了一条边而已啦！
基环树，又叫环套树，是一种由点和边组成的图，含有一个环，而环上的每一个点又是一棵树的树根，即整颗树的根不是一个点而是一个环，所以称之为基环树。
基环树的处理主要分为两部分，大家应该也能想到，树的部分与环的部分（后者一般比较恶心），我们一般的操作就是断开环上的一条边，使其变成一棵树，然后跑DFS或DP。
基环树也分有向图和无向图，有向图中又有两种：内向树和外向树。
内向树指的是每个点只有一条出边的基环树
外向树指的是每个点只有一条入边的基环树
如下图就是一个内向树（外向树把所有边反一下
二.解决方法
1.找环：
无向图：拓扑排序
可以把度数为(1)的点放入一个队列，不断更新，最后度数还剩下(2)的点就在环中，代码如下：
queue <int> q;
inline void topo()
{
for(;!q.empty();)q.pop();
for(re int i=1;i<=n;i++)
if(in[i]==1)q.push(i);
for(re int u;!q.empty();)
{
u=q.front(),q.pop();
for(re int i=hd[u],v;i;i=e[i].net)
{
v=e[i].v,in[v]--;
if(in[v]==1)
q.push(v);
}
}
}
有向图：DFS
这个更简单，直接爆搜，码量也很小！
void dfs(int u)
{
vis[u]=1;
for(re int v,i=hd[u];i;i=e[i].net)
{
v=e[i].v;
if(vis[v])Sign=v;
else dfs(v);
}
}
(Sign) 就是环中的一个点。
2.断环：
我们处理基环树的方式一般就是断开一条环上的边，然后在处理，当然也可以枚举终点和起点，把环上的点放入一个数组并复制一遍，就可以拿一个长度为环上点的个数(n)的区间在上面枚举了。
三.例题：
本题为(2018)年提高(Day2)的题，其中(40)分，也就是(n=m)的情况，考了基环树。
因为(nle5000)，可以(O(n^2))做，所以这题很适合断环，枚举环上的每一条边，打上标记不得走，就变成前(60\%)一样的题了。
讲完，上代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define re register
using namespace std;
int n,m,len[5005],a[5005][5005],lon,ans[5005],in[5005],b[5005],KBL;
bool vis[5005],yor[5005],viss[5005][5005];
void dfs(int u)
{
if(lon==n||KBL==-1)return;
vis[u]=1,lon++;
ans[lon]=u;
if(ans[lon]<b[lon])KBL=1;
else if(ans[lon]>b[lon]&&KBL==0){KBL=-1;return ;}
for(re int i=1;i<=len[u];i++)
if(vis[a[u][i]]==0&&viss[u][i]==0)dfs(a[u][i]);
}
queue <int> q;
inline void topo()
{
for(;!q.empty();)q.pop();
for(re int i=1;i<=n;i++)
if(in[i]==1)q.push(i);
for(re int u;!q.empty();)
{
u=q.front(),q.pop();
for(re int i=1;i<=len[u];i++)
if(in[a[u][i]])
{
in[a[u][i]]--;
if(in[a[u][i]]==1)
q.push(a[u][i]);
}
}
}
int main()
{
memset(b,63,sizeof(b));
scanf("%d%d",&n,&m);
for(re int i=1,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
in[x]++,in[y]++;
a[x][++len[x]]=y;
a[y][++len[y]]=x;
}
for(re int i=1;i<=n;i++)sort(a[i]+1,a[i]+len[i]+1);
if(n==m+1)
{
dfs(1);
for(re int i=1;i<=lon;i++)
b[i]=ans[i];
}
else if(n==m)
{
memset(b,63,sizeof(b));
topo();
for(re int i=1;i<=n;i++)
{
if(in[i]<2)continue;
for(re int j=1;j<=len[i];j++)
{
if(in[a[i][j]]<2)continue;
viss[i][j]=1,lon=0,KBL=0;
memset(vis,0,sizeof(vis));
dfs(1);
viss[i][j]=0;
if(KBL==1)
for(re int k=1;k<=n;k++)
b[k]=ans[k];
}
}
}
for(re int i=1;i<=n;i++)printf("%d ",b[i]);
return 0;
}
这题是在本蒟蒻没学领接表的时候写的，所以存边的方式有点。。
分析一下题目，发现就是基环树森林版的没有上司的舞会，所以我们就可以枚举每一颗基环树，随便断开其中一条边，跑DP就行了，不过因为断了一条边，所以那一条边必须有一端不能取，所以各枚举两端强行不取的情况就完成了。
剩下的就和没有上司的舞会一样了。。
手起，码落：
#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define re register
#define inf 1e18
using namespace std;
const int N=1000005;
struct edge{int v,net;}e[N];
int n,a[N],fa[N],rt,cnt,hd[N];
bool vis[N];
long long f[N][2],ans;
inline void add(int u,int v){e[++cnt].v=v,e[cnt].net=hd[u],hd[u]=cnt;}
void DP(int u)
{
vis[u]=1,f[u][0]=0,f[u][1]=a[u];
for(re int i=hd[u],v;i;i=e[i].net)
{
v=e[i].v;
if(v==rt){f[v][1]=-inf;continue;}
DP(v);
f[u][1]+=f[v][0];
f[u][0]+=max(f[v][0],f[v][1]);
}
}
inline void work(int x)
{
rt=x,vis[rt]=1;
for(;vis[fa[rt]]==0;rt=fa[rt],vis[rt]=1);
DP(rt);
re long long mid=f[rt][0];
rt=fa[rt];
DP(rt);
ans+=max(mid,f[rt][0]);
}
int main()
{
scanf("%d",&n);
for(re int i=1;i<=n;i++)
scanf("%d%d",&a[i],&fa[i]),add(fa[i],i);
for(re int i=1;i<=n;i++)
if(vis[i]==0)work(i);
printf("%lld",ans);
return 0;
}