2018.10.29 bzoj1023: [SHOI2008]cactus仙人掌图（仙人掌+单调队列优化dp）

传送门 求仙人掌的直径。 感觉不是很难。

---

分点在环上面和不在环上分类讨论。 不在环上直接树形$dp$。 然后如果在环上讨论一波。 首先对环的祖先有贡献的只有环上$dfs$序最小的点。 对答案有贡献的则是环上的任意两个点。 对于环上任意两点$(i,j)$ $Ans=max(Ans,f[i]+f[j]+dist(i,j))$其中$dist$指的是较短的距离。 假设$i>j$那么$f[i]+f[j]+i-j$这个式子可以用单调队列优化。 然后均摊下来每次复杂度是当前环长度。 因此总复杂度$O(n)$ 代码：

#include<bits/stdc++.h> using namespace std; inline int read(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans; } const int N=2e5+5,M=1e6+5; int n,m,first[N],cnt=0,tot=0,fa[N],dep[N],f[N],dfn[N],low[N],q[N<<1],a[N<<1],hd,tl,ans=0; struct edge{int v,next;}e[M<<1]; inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;} inline void update(int st,int ed){ int siz=dep[ed]-dep[st]+1,lim=siz>>1,all=siz; for(int pos=ed,i=siz;i;--i,pos=fa[pos])a[i]=pos; memcpy(a+siz+1,a+1,sizeof(int)*lim),siz+=lim,q[hd=tl=1]=1; for(int i=2;i<=siz;++i){ while(hd<=tl&&q[hd]<i-lim)++hd; ans=max(ans,f[a[i]]+f[a[q[hd]]]+i-q[hd]); while(hd<=tl&&f[a[q[tl]]]-q[tl]<=f[a[i]]-i)--tl; q[++tl]=i; } for(int i=2;i<=all;++i)f[st]=max(f[st],f[a[i]]+min(i-1,all-i+1)); } inline void tarjan(int p){ dfn[p]=low[p]=++tot; for(int i=first[p];i;i=e[i].next){ int v=e[i].v; if(v==fa[p])continue; if(!dfn[v])fa[v]=p,dep[v]=dep[p]+1,tarjan(v),low[p]=min(low[p],low[v]); else low[p]=min(low[p],dfn[v]); if(dfn[p]<low[v])ans=max(ans,f[p]+f[v]+1),f[p]=max(f[p],f[v]+1); } for(int i=first[p];i;i=e[i].next){ int v=e[i].v; if(fa[v]!=p&&dfn[p]<dfn[v])update(p,v); } } int main(){ n=read(),m=read(); while(m--){ int k=read()-1,x=read(),y; while(k--)y=read(),add(x,y),add(y,x),x=y; } tarjan(1),cout<<ans; return 0; }