Luogu_P4381 [IOI2008]Island
基环树
题目链接
题目描述的就是一个基环树森林
每次必须要用船的就是两棵基环树之间转移
考虑每个基环树的贡献
有两种可能
第一种是不在环上的一条最长的链，也就是直径
第二种是经过环
第一种很好处理，DP求直径
第二种则在DP的时候记录(d[i])表示(i)能到达的最远距离
这样可以断环为链，(d[i]+d[j]+dis(i,j))最大值(dis)是环上的距离
然后就可以单调队列维护进行DP
弹队头是(i，j)已经超过一圈
队尾则是通过推式子来取最优
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2*1e6+10;
ll ans=0,d[maxn],ff[maxn<<1];
int n,head[maxn],tot=1,v[maxn],ins[maxn],top,q[maxn];
vector<pair<int,ll> > s;
pair<int,ll> st[maxn];
bool in[maxn],hv[maxn],vis[maxn<<1];
struct node{
int nxt,to,dis;
#define nxt(x) e[x].nxt
#define to(x) e[x].to
#define dis(x) e[x].dis
}e[maxn<<1];
inline void add(int from,int to,int w){
to(++tot)=to;dis(tot)=w;
nxt(tot)=head[from];head[from]=tot;
}
void dfs(int x){
for(int i=head[x];i;i=nxt(i)){
int y=to(i),w=dis(i);
if(v[y]){
if(!vis[i^1]){
for(int j=ins[y]+1;j<=top;j++){
s.push_back(st[j]);in[st[j].first]=1;
}
s.push_back(make_pair(y,(ll)w));
in[y]=vis[i]=1;
}
continue;
}
v[y]=vis[i]=1;
st[++top]=make_pair(y,(ll)w);
ins[y]=top;
dfs(y);
--top;
}
}
void dp(int x,ll &now){
hv[x]=1;
for(int i=head[x];i;i=nxt(i)){
int y=to(i);
if(in[y] || hv[y]) continue;
dp(y,now);
ll w=(ll)dis(i);
now=max(now,d[x]+d[y]+w);
d[x]=max(d[x],d[y]+w);
}
}
inline ll tr(int x){
s.clear();v[x]=ins[x]=top=1;
st[1]=make_pair(x,0);
dfs(x);
ll now=0;
for(unsigned int i=0;i<s.size();i++)
dp(s[i].first,now);
int siz=s.size();
for(int i=0;i<siz;i++)
s.push_back(s[i]);
int l=0,r=0;q[0]=0;
for(unsigned int i=1;i<s.size();i++){
ff[i]=ff[i-1]+s[i].second;
ll val=d[s[i].first]-ff[i];
while(l<r && q[r]-q[l]>=siz-1) l++;
now=max(now,ff[i]+d[s[i].first]+d[s[q[l]].first]-ff[q[l]]);
while(l<r && d[s[q[r]].first]-ff[q[r]]<=val) r--;
q[++r]=i;
}
return now;
}
int main(){
scanf("%d",&n);
for(int y,z,i=1;i<=n;i++){
scanf("%d%d",&y,&z);add(i,y,z);add(y,i,z);
}
for(int i=1;i<=n;i++)if(!v[i]) ans+=tr(i);
printf("%lld
",ans);
return 0;
}