小型仙人掌，【仙人掌直径】P4244 [SHOI2008]仙人掌图 II

题目链接https://www.luogu.org/problem/P4244

题意

仙人掌：无向图，任何一条边至多在一个环内。
直径：任意两点最短路(边权为$1$)的最大值。

题解

普通树上求直径可以写成$dp$的形式，$dp[u]$代表$u$子树内以$u$为端点的最长链，树形$dp$做一遍搜索即可。

• 答案更新为：$ans=max(dp[u]+dp[v]+1)$
• $dp$更新为：$dp[u]=max(dp[v]+1)$。

对于仙人掌的情况，也是可以搜索去转移的。
如果$u-v$的边是桥，那么转移方程是跟上面说的树的情况是一样的。
如果$u-v$的边是在环内：

• 首先环内任意两点距离能够根据深度很方便的求出，那么答案就可以由环内的点$x,y$来更新：$ans=dis(x,y)+dp[x]+dp[y]$，这个具体的可以用单调队列维护来实现。
• 对于这个环的根，也就是$u$，我们可以更新它的$dp值$，$dp[u]=max(dp[v]+dis(u,v))$，$v$是环内一点。

而在搜索过程中判断$u-v$的边是不是桥，可以直接利用$Tarjan$算法，所以直接在$Tarjan$的时候更新就行了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
struct Edge{int v,nxt;
}e[N*2];
int p[N],edn;
void add(int u,int v){e[++edn]=(Edge){v,p[u]};p[u]=edn;e[++edn]=(Edge){u,p[v]};p[v]=edn;
}
int n,m;
int a[N],tot;
int fa[N],dt[N],dp[N],ans;
int dfn[N],low[N],cnt;
deque<int>dq;
void solve(int rt,int now){tot=1;a[1]=dp[rt];while(now!=rt) a[++tot]=dp[now],now=fa[now];for(int i=tot+1;i<=tot*2;i++) a[i]=a[i-tot];while(!dq.empty()) dq.pop_back();dq.push_back(1);for(int i=2;i<=tot*2;i++){while(!dq.empty()&&(i-dq.front())>tot/2) dq.pop_front();ans=max(ans,i-dq.front()+a[dq.front()]+a[i]);while(!dq.empty()&&a[dq.back()]+i-dq.back()<=a[i]) dq.pop_back();dq.push_back(i);}for(int i=1;i<=tot;i++){dp[rt]=max(dp[rt],min(i-1,tot-i+1)+a[i]);}
}
void dfs(int u){dfn[u]=low[u]=++cnt;dp[u]=0;for(int i=p[u];~i;i=e[i].nxt){int v=e[i].v;if(v==fa[u]) continue;if(!dfn[v]){fa[v]=u;dt[v]=dt[u]+1;dfs(v);}low[u]=min(low[u],low[v]);if(low[v]>dfn[u]) ans=max(ans,dp[u]+dp[v]+1),dp[u]=max(dp[u],dp[v]+1);}for(int i=p[u];~i;i=e[i].nxt){int v=e[i].v;if(fa[v]==u||dfn[v]<dfn[u]) continue;solve(u,v);}
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) p[i]=-1;edn=-1;while(m--){scanf("%d",&tot);for(int i=1;i<=tot;i++){scanf("%d",&a[i]);if(i>1) add(a[i-1],a[i]);}}dfs(1);printf("%d\n",ans);
}