P4381 [IOI2008] Island
方杰123
·
·
个人记录
题目
思路
题目简化后就是：给定一片基环树森林，求每个基环树的直径之和。
那么我们意识到一棵树可能长这样：
（其实是双向边，箭头是题目给的方向）
接下来考虑答案不经过环，那么答案就是所有环的子树的直径。可以发现其他点都是一步步指向根，环是按一个方向顺次连接。所以只要做一遍拓扑排序，即可更新到所有不包含环的点。设计g[i]表示i这个点的子树的直径，f[i]表示i到他的叶子的最大距离。
g[to[u]]=max(g[to[u]],g[u]);//儿子的最大直径也可以是我的最大直径
g[to[u]]=max(g[to[u]],f[to[u]]+f[u]+w[u]);//最长边和现在的边可以构成一个新的可能的最长直径
f[to[u]]=max(f[to[u]],f[u]+w[u]);//更新f[u]
然后考虑答案经过环，那么答案即为max(f[i]+f[j]+dis(i,j))，（dis指环上距离），枚举n^2直接离世，那么考虑前缀和优化:
如图：
红色是我们找到的环的入口，那么假设我们顺着环走，现在要更新绿色的点，答案即为
```cpp
int now=to[u];int res=g[u];int dis=w[u],st=f[u];
while(now!=u){
ind[now]=0;
res=max(res,g[now]);//顺便求出不经过环的最大的树的直径
res=max(res,st+dis+f[now]);
st=max(st,f[now]-dis);
dis+=w[now];
now=to[now];
}
```
最后，再按环反方向维护一次即可。
## code
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
int ans,dis[N],n,to[N],ind[N],w[N],f[N],g[N];
queue<int>q;
int work(int u){
ind[u]=0;
int now=to[u];int res=g[u];int dis=w[u],st=f[u],st2=f[u];
int res2=-1e10;//res2为反方向维护的最大值
while(now!=u){
ind[now]=0;
res=max(res,g[now]);
res=max(res,st+dis+f[now]);
res2=max(res2,st2-dis+f[now]);
st=max(st,f[now]-dis);
st2=max(st2,f[now]+dis);
dis+=w[now];
now=to[now];
}
return max(res,res2+dis);//res2是算减掉哪些边，最后加上整个环长
}
signed main(){
n=read();
for(int i=1;i<=n;i++){to[i]=read(),w[i]=read(),ind[to[i]]++;}
for(int i=1;i<=n;i++)if(ind[i]==0)q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
ind[to[u]]--;if(!ind[to[u]])q.push(to[u]);
g[to[u]]=max(g[to[u]],f[to[u]]+f[u]+w[u]);
g[to[u]]=max(g[to[u]],g[u]);
f[to[u]]=max(f[to[u]],f[u]+w[u]);
}
for(int i=1;i<=n;i++)if(ind[i])ans+=work(i);
printf("%lld",ans);
return 0;
}
```