題目鏈接

類似求樹的直徑，可以用(類似)樹形DP求每個點其子樹(在仙人掌上就是誘導子圖)最長鏈、次長鏈，用每個點子節點不同子樹的 max{最長鏈}+max{次長鏈} 更新答案。(不需要存次長鏈，求解過程中先更新ans，然后再更新最長鏈即可)
設f[i]為點i的誘導子圖中最長鏈的長度。
對于環，我們找一個環上dep[]最小的點x代表這個環 看做一個點(dep為按DFS順序更新的)，求出f[x]，環以外的部分像樹一樣直接做就可以。
對于環的處理：f[x]比較顯然，f[x]=max{f[v]+dis(x,v)}，v為其環上一點，dis(x,v)為x,v在環上的最小距離。
環上如何更新答案？把環上所有點都拿出來，ans=max{f[u]+f[v]+dis(u,v)}。
u,v是環上的點，按順序編號，dis(u,v)=v-u(v-u<=len/2)，那么ans可以寫成 max{f[u]-u+f[v]+v}。固定v，因為u是單增的，所以之前最大的f[u]-u在后面也是最大的，可以用單調隊列維護。
dis()是環上最小距離，所以v-u不能超過 環長/2。因為是個環，所以把它拆成一個3/2*len的序列更新ans。
之后用f[v]+dis(x,v)更新f[x]。
掃一遍所有的環，總共復雜度是\(O(m)\)。

總：Tarjan，對于不在同一環上的點，用f[x]+f[v]+1更新ans，再用f[v]更新f[x]；對于其它的點，像上面那樣取出環單調隊列處理。

//8760kb 192ms #include <cstdio> #include <cctype> #include <algorithm> #define gc() getchar() const int N=5e4+5,M=N<<2;//邊數。。大概最多2n條？int n,m,Ans,Enum,H[N],to[M],nxt[M],dfn[N],low[N],id,fa[N],dep[N],f[N],q[N],A[N<<1];inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } inline void AddEdge(int u,int v){to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum; } void DP(int x,int ed) {int n=dep[ed]-dep[x]+1;//lengthfor(int i=n; i; --i) A[i]=f[ed], ed=fa[ed];int n2=n+(n>>1);//能同時更新別的的最多只有n/2個點，所以只需要3/2*n for(int i=n+1; i<=n2; ++i) A[i]=A[i-n];int h=1,t=1; q[1]=1;for(int i=2; i<=n2; ++i)//i,q[]是點，拿出來的A[]是f[]！{while(h<t && i-q[h]>(n>>1)) ++h;Ans=std::max(Ans,A[q[h]]-q[h]+A[i]+i);while(h<=t && A[q[t]]-q[t]<=A[i]-i) --t;//注意這個比較是<，因為更新隊首時不是根據值的大小，而是限制條件(<=竟然有90...) q[++t]=i;}for(int i=2; i<=n; ++i)f[x]=std::max(f[x],A[i]+std::min(i-1,n-i+1)); } void DFS(int x) {dfn[x]=low[x]=++id;for(int v,i=H[x]; i; i=nxt[i])if((v=to[i])!=fa[x]){if(!dfn[v])fa[v]=x, dep[v]=dep[x]+1, DFS(v), low[x]=std::min(low[x],low[v]);if(low[v]>dfn[x])//不是環 Ans=std::max(Ans,f[x]+f[v]+1), f[x]=std::max(f[x],f[v]+1);low[x]=std::min(low[x],dfn[v]);//無向圖，就不需要什么在棧中了 //只需判環，所以和下一行寫法一樣 // low[x]=std::min(low[x],low[v]);}for(int i=H[x]; i; i=nxt[i])if(fa[to[i]]!=x&&dfn[to[i]]>dfn[x]) DP(x,to[i]);//找環的另一個端點 //端點是后訪問的點，而不只是&&to[i]!=fa[x]！(當x同時在兩個環上時)能找到之前的環和x之后的環，但x不代表(沒必要)之前訪問的環，這樣找環還麻煩。。不是沿to[i]的fa到x。 }int main() {n=read(),m=read();int num,u,v;while(m--){num=read()-1, u=read();while(num--) v=read(),AddEdge(u,v),u=v;}DFS(1);printf("%d",Ans);return 0; }

轉載于:https://www.cnblogs.com/SovietPower/p/8976378.html

總結

以上是生活随笔為你收集整理的BZOJ.1023.[SHOI2008]cactus仙人掌图(DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。