Luogu

分析

设 $f_i$ 表示 $i$ 子树中以 $i$ 为端点的最长链的长度。

如果当前边是桥，直接转移，同时更新 $ans$ 。

否则当前边在环上，先不处理。

假设我们现在在 $u$，$v$ 已经被访问过了。那么 $u$ 是这个环的底端， $v$ 是这个环的顶端。

我们把这个环找出来单独考虑。

先考虑怎么用环上的点更新答案。

要求的实际上是 $\max\{f_i+f_j+dis(i,j)\}$ ，这里的 $dis(i,j)=\min(|dep[i]-dep[j]|,sz-|dep[i]-dep[j]|)$ 。

把环按照深度排序后倍长，然后维护一个单调队列，即可得到出每个 $i$ 最优的 $j$，然后更新答案。

最后枚举环上的点更新环顶端的 $f$ 值即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;
const int M=500000+10;

struct Edge { int v,nxt; } e[M];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int ans=0;
int dfn[N],low[N],tim=0;
int fa[N],dep[N],f[N];
int seq[N<<1],Q[N<<1];

inline void dp(int u,int v) { //环上的dp
    int tot=0,h=1,t=0;
    for (re int i=v;i!=u;i=fa[i]) seq[++tot]=i; seq[++tot]=u;
    reverse(seq+1,seq+tot+1);
    for (re int i=1;i<=tot;++i) seq[i+tot]=seq[i];
    for (re int i=1;i<=(tot<<1);++i) {
        while (h<=t&&i-Q[h]>tot/2) ++h;
        if (h<=t) ans=max(ans,f[seq[i]]+f[seq[Q[h]]]+i-Q[h]);
        while (h<=t&&f[seq[i]]-i>f[seq[Q[t]]]-Q[t]) --t;
        Q[++t]=i;
    }
    for (re int i=v;i!=u;i=fa[i])
        f[u]=max(f[u],f[i]+min(dep[i]-dep[u],dep[v]-dep[i]+1));
}

inline void tarjan(int u,int pa) {
    dfn[u]=low[u]=++tim;
    fa[u]=pa,dep[u]=dep[pa]+1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) tarjan(v,u),low[u]=min(low[u],low[v]);
        else if (v!=pa) low[u]=min(low[u],dfn[v]);
        if (low[v]>dfn[u]) ans=max(ans,f[u]+f[v]+1),f[u]=max(f[u],f[v]+1);
    }
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (u!=fa[v]&&dfn[u]<dfn[v]) dp(u,v);
    }
}

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int k=read(),u=read();
        for (re int j=1;j<k;++j) {
            int v=read();
            addEdge(u,v),addEdge(v,u);
            u=v;
        }
    }
    tarjan(1,0);
    printf("%d\n",ans);
    return 0;
}