BZOJ1791 [Ioi2008]Island 岛屿[基环树+单调队列优化DP]

时间：2025-02-26 16:02:50

基环树直径裸题。

首先基环树直径只可能有两种形式：每棵基环树中的环上挂着的树的直径，或者是挂在环上的两个树的最大深度根之间的距离之和。

所以，先对每个连通块跑一遍，把环上的点找出来，然后对环上每个点跑一遍树的直径（这里采用DP形式，可以顺便求出最大深度，注意DP树的直径方法。。就是考虑跨过每个点的链。。见lyd书树的直径一章）。

然后就变成了环上每个点有权值，求最大价值。`````

基环树上的环处理起来方法比较多，这里由于是DP，采用断环成链的方法，把环复制两遍，然后对第二份进行DP，就可以转化为1D1DDP，然后显然就可以单调队列优化了。

bzoj栈没开大，所以要手写递归栈或者用其他方法。。不想写了，所以直接在luogu交了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define mst(x) memset(x,0,sizeof x)

 #define dbg(x) cerr << #x << " = " << x <<endl

 #define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=1e6+;

 struct thxorz{

     int head[N],nxt[N<<],to[N<<],w[N<<],tot;

     thxorz(){tot=;}

     inline void add(int x,int y,int z){

         to[++tot]=y,nxt[tot]=head[x],head[x]=tot,w[tot]=z;

         to[++tot]=x,nxt[tot]=head[y],head[y]=tot,w[tot]=z;

     }

 }G;

 int n,m;

 #define y G.to[j]

 int vis[N],lp[N<<],q[N],l,r,lpfa,cir,flag;

 ll d[N],sum[N<<],ans,res;

 void dfs(int x,int fa){//dbg(x);

     vis[x]=;

     for(register int j=G.head[x];j&&!flag;j=G.nxt[j])if(j^(fa^)){//dbg(y);

         if(!vis[y]){

             dfs(y,j);

             if(flag)lp[++m]=x,sum[m]=sum[m-]+G.w[j];

         }

         else return lpfa=y,lp[m=]=x,sum[]=G.w[j],flag=,void();

     }

     if(!flag)vis[x]=;

     if(x==lpfa)flag=;

 }

 void dp(int x){//dbg(x);

     vis[x]=;

     for(register int j=G.head[x];j;j=G.nxt[j])if(!vis[y])

         dp(y),MAX(ans,d[y]+d[x]+G.w[j]),MAX(d[x],d[y]+G.w[j]);

 }

 #undef y

 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);

     read(n);

     for(register int i=,y,z;i<=n;++i)read(y),read(z),G.add(i,y,z);

     for(register int i=;i<=n;++i)if(!vis[i]){

         l=,r=ans=m=;dfs(i,);//dbg2("ok loop",m);

         for(register int j=;j<=m;++j)dp(lp[j]);//dbg2("ok tree",lp[j]);

         for(register int j=;j<=m;++j){

             while(l<=r&&d[lp[j]]-sum[j]>=d[lp[q[r]]]-sum[q[r]])--r;

             q[++r]=j;

         }

         for(register int j=m+;j<=m<<;++j){

             while(l<=r&&q[l]<=j-m)++l;

             sum[j]=sum[m]+sum[j-m],lp[j]=lp[j-m];

             MAX(ans,d[lp[q[l]]]+d[lp[j]]+sum[j]-sum[q[l]]);

             while(l<=r&&d[lp[q[r]]]-sum[q[r]]<=d[lp[j]]-sum[j])--r;

             q[++r]=j;

         }

         res+=ans;

     }

     printf("%lld\n",res);

     return ;

 }

总结：环上问题多有断环成链做法。

相关文章