#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 51000
using namespace std;
struct node
{
int y,next;
}a[410000];int last[N],len;
inline void ins(int x,int y)
{
len++;a[len].y=y;a[len].next=last[x];last[x]=len;
len++;a[len].y=x;a[len].next=last[y];last[y]=len;
}
inline int read()
{
char c=getchar();int s=0,f=1;
while(c<'0' || '9'<c){if(c=='-')f=-1;c=getchar();}
while('0'<=c && c<='9'){s=s*10+c-'0';c=getchar();}
return f*s;
}
int ans=0,low[N],dfn[N],f[N],fa[N],deep[N],id,e[2*N],list[2*N],head,tail;
inline int mymin(int x,int y){return x<y?x:y;}
inline int mymax(int x,int y){return x>y?x:y;}
inline void dp(int root,int x)
{
int tot=deep[x]-deep[root]+1;
for(int i=x;i!=fa[root];i=fa[i])e[tot--]=f[i];
tot=deep[x]-deep[root]+1;
for(int i=1;i<=tot;i++)e[i+tot]=e[i];
head=tail=1;list[1]=1;
for(int i=2;i<=tot*2;i++)//为什么不能从1开始?
{
while(head<=tail && i-list[head]>tot/2)head++;
ans=mymax(ans,e[list[head]]+e[i]+i-list[head]);
while(head<=tail && e[list[tail]]-list[tail]<=e[i]-i)tail--;
list[++tail]=i;
}
for(int i=2;i<=tot;i++)f[root]=mymax(f[root],e[i]+mymin(i-1,tot-i+1));
}
inline void dfs(int x)
{
dfn[x]=low[x]=++id;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y==fa[x])continue;
if(!dfn[y])
{
fa[y]=x;
deep[y]=deep[x]+1;
dfs(y);
low[x]=mymin(low[x],low[y]);
}
else low[x]=mymin(low[x],dfn[y]);//为什么不能去掉mymin?
if(low[y]>dfn[x])
{
ans=mymax(ans,f[y]+f[x]+1);
f[x]=mymax(f[x],f[y]+1);
}
}
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(fa[y]!=x && dfn[x]<dfn[y])dp(x,y);
}
}
int main()
{
int n=read(),m=read();
for(int i=1;i<=m;i++)
{
int x,y,k;k=read();x=read();
for(int j=2;j<=k;j++)
{
y=read();
ins(x,y);
x=y;
}
}
id=ans=0;
dfs(1);
printf("%d\n",ans);
return 0;
}
问题在代码里面斜杠标注
1.for那里为什么不能从1开始,就算重叠了感觉也没什么影响啊?(从1开始就wa掉了)
2.为什么不能去掉mymin? 直接else low[x]=dfn[y]?如果y不是x的爸爸且被访问过但是low[x]却小于dfn[y],不就是两环共边的情况吗?不符合仙人掌树的定义呀。