【题意】给定仙人掌图（每条边至多在一个简单环上），求直径（最长的点对最短路径）。n<=50000,m<=10^7。

【算法】DFS树处理仙人掌

【题解】参考：

对仙人掌建立DFS树，参考无向图的点双连通分量Tarjan算法，在访问x时容易知道边(x,y)是否属于一个环。

设f[x]表示x点向下延伸的最长链长度，对于不在环上的边(x,y)，有f[x]=max{f[y]+1}。统计直径可以在访问每个y时进行ans=max{ans,f[x]+f[y]+1}从而完成子树x对答案的贡献。

对于一个环，只在其DFS树中深度最小的点进行处理（其它点直接忽略环边的存在），假设当前这个点为x，其与深度最大的点y的连边为(x,y)。（这条边只要满足fa[y]≠x&&dfn[y]>dfn[x]就可以找到）

假设这个环有cnt个点，在环上只有距离<=cnt/2的点对可以贡献答案。我们只需要维护每个点和其前面半圈的点构成的点对中的最大值，这可以用单调队列维护。

但这样的话，前半圈的点与前面的点对会少考虑一部分，所以将环延伸半圈，即维护一圈半的点。最后记得枚举整个环更新f[x]。

复杂度O(m)。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int maxn=100010,maxm=20000010;struct edge{
    int v,from;}e[maxm];int first[maxn],tot,fa[maxn],a[maxn],f[maxn],q[maxn],dfn[maxn],low[maxn],ans,dfsnum=0,n,m;void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}void solve(int A,int B){    int cnt=0;    for(int i=B;i!=A;i=fa[i])a[++cnt]=f[i];a[++cnt]=f[A];    for(int i=1;i<=cnt/2;i++)swap(a[i],a[cnt-i+1]);    for(int i=cnt+1;i<=cnt+(cnt>>1);i++)a[i]=a[i-cnt];    int head=0,tail=1;q[head]=1;    for(int i=2;i<=cnt+(cnt>>1);i++){        if(head
          
           cnt/2)head++;        ans=max(ans,a[i]+a[q[head]]+i-q[head]);        while(head
           
            =a[q[tail-1]]-q[tail-1])tail--; q[tail++]=i; } for(int i=2;i<=cnt;i++)f[A]=max(f[A],a[i]+min(i-1,cnt-i+1));}void dfs(int x,int father){ dfn[x]=low[x]=++dfsnum;f[x]=0; for(int i=first[x];i;i=e[i].from)if(e[i].v!=father){ int y=e[i].v; if(!dfn[y]){ fa[y]=x; dfs(y,x); low[x]=min(low[x],low[y]); }else low[x]=min(low[x],dfn[y]); if(low[y]>dfn[x]){ ans=max(ans,f[x]+f[y]+1); f[x]=max(f[x],f[y]+1); } } for(int i=first[x];i;i=e[i].from) if(e[i].v!=father&&fa[e[i].v]!=x&&dfn[e[i].v]>dfn[x])solve(x,e[i].v);} int main(){ n=read();m=read(); for(int i=1;i<=m;i++){ int k=read(),u=read(); for(int j=2;j<=k;j++){ int v=read(); insert(u,v);insert(v,u); u=v; } } ans=0; dfs(1,0); printf("%d",ans); return 0;}