题解 P6335 【[COCI2007-2008#1] STAZA】
panyf
·
·
题解
提供一个更简单的仙人掌 dp 做法。
设 f_i 表示从 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 找环即可。
```cpp
#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;
}
```