题意：
给你一棵基环树森林，求出基环树的直径之和.
题解：
对于基环树,我们将环看作根,那么直径有两种情况::
1.不经过环,也就是环上某个点的子树内部,对于这种情况,直接在子树内部处理直径,更新答案即可;
2.经过环,答案就是i的子树内长度+j的子树内长度+i和j之间的距离，我们预处理出环上每个点到其子树上的最长距离,在预处理一个环上前缀和,ans=max{sondis[i]+sondis[j]+sumcircle[i]-sumcircle[j]},更新答案即可.
sondis[i]记录环上的第i个点到其子树的最远距离;
sumcircle[]记录环上距离前缀和;
sumcircle[i]-sumcircle[j]即为i和j的距离
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e6+3;
int to[N<<1],nex[N<<1],head[N],w[N<<1],tt;
int c[N];//记录当前节点属于第几棵基环树;
int dg[N];//记录度数;
int q[N<<1];//数组模拟队列;
ll d[N];//d[i]记录第i棵树上的直径;
ll f[N];//f[i]记录从i点向儿子方向上所可以走的最长距离;
ll sumcircle[N<<1];//环上距离前缀和;
ll sondis[N<<1];//sondis[i]记录环上的第i个点到其子树的最远距离;
int cnt,n;
bool vis[N];//标记当前基环树是否已解决过;
inline void add(int x,int y,int W){
to[++tt]=y,w[tt]=W,nex[tt]=head[x],head[x]=tt;
return ;
}
inline void bfs(int p,int t){
int l=0,r=1;
q[1]=p,c[p]=t;//广搜预处理每一个点所属基环树的编号;
while(l<r){
++l;
int x=q[l];
for(int i=head[x],v;i;i=nex[i]){
v=to[i];
if(!c[v]){
q[++r]=v;
c[v]=t;
}
}
}
return ;
}
inline void top_sort(){//拓扑排序求不经过环的直径,从叶子节点向根(环)遍历;
int l=0,r=0;
for(int i=1;i<=n;++i)if(dg[i]==1)q[++r]=i;//将所有度数为1的点先加入队列中(即叶子结点);
while(l<r){
++l;
int x=q[l];
for(int i=head[x],v;i;i=nex[i]){
v=to[i];
if(dg[v]>1){//此时v在以环为根的树上是其实是x的父亲;
d[c[x]]=max(d[c[x]],f[x]+f[v]+w[i]);//更新当前基环树上的答案;
f[v]=max(f[v],f[x]+w[i]);//更新父节点可以到达的最远节点;
if(--dg[v]==1)q[++r]=v;//若当前度数现在变为1,入队;
}
}
}
return ;
}
inline void work(int t,int x){
int tot=0,l,r,v=x,u,i;//在拓扑排序后已经将非环上的边遍历完了,环上的边和点均还未遍历,且度数为2,将x看做环上的起点,v看做终点;
do{
dg[v]=1;
sondis[++tot]=f[v];//将当前点度数记为1,防止反向遍历,同时记录第tot号环上节点到子树上的最短距离;
for(i=head[v];i;i=nex[i]){
u=to[i];
if(dg[u]>1){//环上的点度数均大于1,所以度数大于1的点即是环上的点;
v=u;//更新终点;
sumcircle[tot+1]=sumcircle[tot]+w[i];//处理环上距离前缀和;
break;//保证向一边枚举,所以找到一个点就break;
}
}
}while(i);
if(tot==2){//特殊处理二元环;
int len=0;
for(i=head[v];i;i=nex[i]){
u=to[i];
if(u==x){
len=max(len,w[i]);//找出两个点之间较大的边;
}
}
d[t]=max(d[t],(ll)len+f[x]+f[v]);//更新答案;
return ;
}
for(int i=head[v],u;i;i=nex[i]){
u=to[i];
if(u==x){
sumcircle[tot+1]=sumcircle[tot]+w[i];//将起点和终点的距离处理出来;
break;
}
}
for(i=1;i<tot;i++)//断环为链,再复制一遍数组;
{
sondis[tot+i]=sondis[i];
sumcircle[tot+i]=sumcircle[tot+1]+sumcircle[i];
}
q[1]=1;
l=r=1;
for(int i=2;i<tot<<1;++i){
while(l<=r&&i-q[l]>=tot)++l;//将超出环长度的部分弹出;
d[t]=max(d[t],sondis[q[l]]+sondis[i]+sumcircle[i]-sumcircle[q[l]]);
while(l<=r&&sondis[q[r]]+sumcircle[i]-sumcircle[q[r]]<=sondis[i])--r;//将队尾答案不够优秀的部分弹出;
q[++r]=i;//入队;
}
return ;
}
int main(){
cin>>n;
int x,W;
for(int i=1;i<=n;++i)
{
scanf("%d%d",&x,&W);
add(x,i,W);
add(i,x,W);
++dg[x];
++dg[i];
}
for(int i=1;i<=n;++i)if(!c[i])bfs(i,++cnt);//预处理;
top_sort();//拓扑排序求直径;
ll ans=0;
for(int i=1;i<=n;++i)
if(dg[i]>1&&!vis[c[i]]){//如果当前基环树未被处理,并且当前点是环上点,就处理;
vis[c[i]]=true;
work(c[i],i);
ans+=d[c[i]];//累加答案;
}
cout<<ans<<'\n';
return 0;
} 
京公网安备 11010502036488号