仙人掌 之 直径

 

/**************************************************************
    Problem: 1023
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:260 ms
    Memory:7784 kb
****************************************************************/
 
/*
    圆方树 之 仙人掌的直径
    先构造圆方树
    之后和处理树的直径差不多
    该点为圆点则一模一样 记录最深和次深
    该点为方点 更新最深还好 循环一遍就出来了
        主要是更新ans 因为真实距离是两点间的对短距离+深度
        然后咱们可以固定i ，求对于每一个i的max (F[j]+dist(i,j))，
        dist(i,j)等于 min(j-i,n-i+j)，
        为了丢掉这个min好使用单调队列，咱们将环复制一遍，
        然后每一次只考虑半个环长度的DP，这显然是正确的，
        每一个状态都可以在 i 或者 j 的时候被计算到。
        那么方程可以继续改写为 max（F[i]+F[j]+j-i)，
        固定i之后就是求 max(F[j]+j)(j∈[i+1,i+n/2]）
        之后就是单调队列的事情了    口胡。。。 
*/
#include<cstdio> 
#include<cstring>
#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a>b)?(b):(a))
using namespace std;
const int N=100050;
struct pp {int v,nxt;} e[N<<1]; 
int n,nn,m,tot=1,kok,head[N];
int low[N],dfn[N],fa[N],f[N];
int ans,a[N],q[N],dep[N];
void Add(int u,int v)
{
    e[++tot].nxt=head[u];head[u]=tot;e[tot].v=v;
    e[++tot].nxt=head[v];head[v]=tot;e[tot].v=u;
}
void Init()
{
    scanf("%d%d",&n,&m);nn=n;
    for(int i=1;i<=m;i++)
    {
        int num,u=0;scanf("%d",&num);
        for(int j=1,v;j<=num;j++)
        {
            scanf("%d",&v); if(u!=0) Add(u,v); u=v;
        }
    }
}
void Work(int u,int v)
{
    int all=dep[v]-dep[u]+1,j=all;
    for(int i=v;i!=u;i=fa[i]) a[j--]=f[i]; a[j]=f[u];
    // 反着存  
    for(int i=1;i<=all;i++) a[i+all]=a[i]; // 复制 为了走到所有情况 
    int l=0,r=0; q[0]=1;
    for(int i=2;i<=all*2;i++)
    {
        while(l<=r&&i-q[l]>all/2) l++;
        ans=max(ans,a[i]+i+a[q[l]]-q[l]);
        while(l<=r&&a[q[r]]-q[r]<a[i]-i) r--;
        q[++r]=i;
    }
    for(int i=2;i<=all;i++)
        f[u]=max(f[u],a[i]+min(i-1,all-i+1)); // 更新 f 
}
void Tarjan(int u,int last)
// Tarjan的时候顺便把答案也算出来吧 难的第二次Dfs 
{
    dfn[u]=low[u]=++kok;
    for(int j=head[u];j;j=e[j].nxt) if(j!=last)
    {
        int v=e[j].v;
        if(!dfn[v])
        {
            fa[v]=u; dep[v]=dep[u]+1; Tarjan(v,j^1);
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],dfn[v]);
        if(low[v]>dfn[u]) // 确保u的最深 不走v这边 
        {
            ans=max(ans,f[u]+f[v]+1);
            f[u]=max(f[u],f[v]+1);
        }
    }
    for(int j=head[u];j;j=e[j].nxt)
    {
        int v=e[j].v;
        if(fa[v]!=u&&dfn[u]<dfn[v]) Work(u,v);
    }
}
void Solve()
{
    Tarjan(1,0); printf("%d\n",ans);
}
int main()
{
    Init();
    Solve();
    return 0;
}