基环树(环套树)
基环树
基环树也叫环套树，就是n个点n条边的连通图，可以发现只有一个环，并且删掉环上任意一个边可以变成一棵树。如果不联通，那么就是基环树森林。
基环树一般分成环和树来分别处理（显然环的处理较为麻烦），那首先得找到环.
找环
-
dfs
int fa[maxn],dfn[maxn],loop[maxn],cnt,idx; void get_lop(int x){ dfn[x]=++idx; for(int i=head[x];i;i=Next[i]){ if(ver[i]==fa[x]) continue; if(dfn[ver[i]]){ if(dfn[ver[i]]<dfn[x]) continue; loop[++cnt]=ver[i]; int y=ver[i]; while(y!=x){ loop[++cnt]=fa[y]; y=fa[x]; } }else{ fa[ver[i]]=x; get_lop(ver[i]); } } } -
拓扑排序
void topsort(){ queue<int> q; for(int i=1;i<=n;++i) if(in[i]==1) q.push(i); while(q.size()){ int x=q.front(); q.pop(); for(int i=he[x];i;i=nx[i]){ if(in[vr[i]]>1){ if(--in[vr[i]]==1) { q.push(vr[i]); } } } } }
骑士（ZJOI2008）
题目大意
求各个基环树的最大攻击力之和
可以对每棵基环树分别进行树上dp，类似没有上司的舞会那道题
#include <iostream>
using namespace std;
int n;
long long a[1000006];
int nx[1000006],he[1000006],vr[1000006],tot;
inline void add(int x,int y){
vr[++tot]=y;
nx[tot]=he[x];
he[x]=tot;
}
bool v[1000006];
int fa[1000006],root;
long long f[1000006][2],ans;
void dp(int x){
v[x]=1;
f[x][0]=0;
f[x][1]=a[x];
for(int i=he[x];i;i=nx[i]){
if(vr[i]!=root){
dp(vr[i]);
f[x][0]+=max(f[vr[i]][0],f[vr[i]][1]);
f[x][1]+=f[vr[i]][0];
}else{
f[vr[i]][1]=-0x3f3f3f3f;
}
}
}
void find_circle(int x){
v[x]=1;
root=x;
while(!v[fa[root]]){
root=fa[root];
v[root]=1;
}
dp(root);
long long res=max(f[root][0],f[root][1]);
v[root]=1;
root=fa[root];
dp(root);
ans+=max(res,max(f[root][0],f[root][1]));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;int x;
for(int i=1;i<=n;++i){
cin>>a[i];
cin>>x;
add(x,i);
fa[i]=x;
}
for(int i=1;i<=n;++i){
if(!v[i]){
find_circle(i);
}
}
cout<<ans<<endl;
return 0;
}基环树的直径
定义
基环树中最长的简单路径被称为基环树的最长链，其长度被称为基环树的直径。这里的简单路径指的是不自交的（不重复经过任何点或边）路径
Island（IOI2008）
题目大意
求各个基环树的直径和
先用dfs或拓扑排序找到基环树的环，把环上的点标记，再对每个点进行dfs，就可以访问以该点为根的子树。
在每棵子树中求出直径。设
#include <iostream>
#include <queue>
using namespace std;
int n;
int nx[2000006],he[1000006],vr[2000006],eg[2000006],tot;
inline void add(int x,int y,int z){
vr[++tot]=y;
eg[tot]=z;
nx[tot]=he[x];
he[x]=tot;
}
int in[1000006],ku[1000006],v[1000006],t,q[2000006];
long long ans,d[1000006],f[1000006],a[1000006],b[1000006];
// 一定要开long long !!!
void topsort(){
queue<int> q;
for(int i=1;i<=n;++i) if(in[i]==1) q.push(i);
while(q.size()){
int x=q.front();
q.pop();
for(int i=he[x];i;i=nx[i]){
if(in[vr[i]]>1){
d[ku[x]]=max(d[ku[x]],f[x]+f[vr[i]]+eg[i]);
f[vr[i]]=max(f[vr[i]],f[x]+eg[i]);// 树的直径
if(--in[vr[i]]==1) {
q.push(vr[i]);
}
}
}
}
}
void dp(int k,int x){
int m=0;// 环上点的数量
int y=x,z=0,len=0;
do{
a[++m]=f[y];// 记录以环上各点为根的子树的直径
in[y]=1;
for(z=he[y];z;z=nx[z]){
if(in[vr[z]]>1){
y=vr[z];
b[m+1]=b[m]+eg[z];// 标记环上的点
break;
}
}
}while(z);
if(m==2){
for(int i=he[y];i;i=nx[i]){
if(vr[i]==x){
len=max(len,eg[i]);
}
}
d[k]=max(d[k],f[x]+f[y]+len);
return;
}
for(int i=he[y];i;i=nx[i]){
if(vr[i]==x){
b[m+1]=b[m]+eg[i];
break;
}
}
for(int i=1;i<m;++i){
a[i+m]=a[i];b[i+m]=b[m+1]+b[i]; // 复制
}
int l,r;
q[l=r=1]=1;// 单调队列
for(int i=2;i<(m<<1);++i){
while(l<=r && i-q[l]>=m) ++l;
d[k]=max(d[k],a[q[l]]+a[i]+b[i]-b[q[l]]);
while(l<=r && a[q[r]]-b[q[r]]<=a[i]-b[i]) --r;
q[++r]=i;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
int x,z;
for(int i=1;i<=n;++i){
cin>>x>>z;
add(x,i,z);
add(i,x,z);
++in[x];++in[i];
}
queue<int> q;
for(int i=1;i<=n;++i){ // 遍历每个连通块
if(ku[i]) continue;
while(q.size()) q.pop();
q.push(i);
ku[i]=++t;
while(q.size()){
x=q.front();
q.pop();
for(int i=he[x];i;i=nx[i]){
if(ku[vr[i]]) continue;
q.push(vr[i]);
ku[vr[i]]=t;
}
}
}
topsort();// 拓扑排序
for(int i=1;i<=n;++i){
if(in[i]>1 && !v[ku[i]]) { // 如果该点入度大于1，那么就是环上的点
v[ku[i]]=1;// 标记
dp(ku[i],i);
ans+=d[ku[i]];// 统计每个基环树最长简单路径
}
}
cout<<ans;
return 0;
}