自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 22:19:47，当前版本为作者最后更新于2020-10-24 22:31:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一个更简单的仙人掌 dp 做法。

设 $f_i$ 表示从 $i$ 点向下走，并且可以回到 $i$，长度的最大值。

$g_i$ 表示不能回到 $i$，长度的最大值。

设 $w=g_i-f_i$。这样就只需求出 $f_i$ 和 $w$，然后 $g_i=f_i+w$。

对于非环边 $(i,j)$，显然不会对 $f_i$ 产生贡献。$w=\max(w,g_j+1)$（表示先走完所有经过 $i$ 的环，然后沿 $(i,j)$ 向下走）。

对于环，对 $f_i$ 的贡献为环的大小加上环上所有点 $j$ 的 $f_j$，设这个贡献为 $u$。再求出 $v$ 表示走到环上某个点 $j$ 然后向下走的最大值。$v=\max(v,\operatorname{dis}(j,i)+\sum_k f_k+g_j)$，其中 $k$ 为 $i$ 到 $j$ 路径上的点（不含 $i$，$j$），从两个方向分别遍历计算即可。则 $w=\max(w,v-u)$。

实现时可以不用建出圆方树，只需要 tarjan 找环即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+3,M=4e4+3;
int he[N],to[M],ne[M],dfn[N],low[N],fa[N],id,d[N],g[N],f[N];
void tar(int x){
	int i=he[x],j,k,w=0,u,v,o;
	for(dfn[x]=low[x]=++id;i;i=ne[i])if((j=to[i])!=fa[x]){
		if(!dfn[j]){
			d[j]=d[x]+1,fa[j]=x,tar(j),low[x]=min(low[x],low[j]);
			if(low[j]>dfn[x])w=max(w,g[j]+1);
		}else low[x]=min(low[x],dfn[j]);
	}
	for(i=he[x];i;i=ne[i])if(dfn[j=to[i]]>dfn[x]&&fa[j]!=x){
		for(k=j,u=1,v=0;k!=x;k=fa[k])v=max(v,u+g[k]),u+=f[k]+1;
		for(f[x]+=u,o=u;j!=x;j=fa[j])o-=f[j]+1,v=max(v,o+g[j]);
		w=max(w,v-u);
	}
	g[x]=f[x]+w;
}
int main(){
	int n,m,i,j,t=0;
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%d",&i,&j);
		ne[++t]=he[i],to[t]=j,he[i]=t;
		ne[++t]=he[j],to[t]=i,he[j]=t;
	}
	tar(1),printf("%d",g[1]);
	return 0;
}