P6335
Erica_N_Contina
·
·
题解
思路
当我们看到“且每条整个交通系统中的每条道路最多是一个环的一部分”时，我们想到了什么？Tarjan 缩点（虽然本题不需要缩点，但是 Tarjan 这条路我们想对了）。
实际上题目要求的就是一个含有简单环的无向图上的最长路径，满足不经过重边。那么我们很显然可以想到圆方树，这样我们就可以把图转化为一副无环的简单图了。
接下来就是在一副简单图中寻找最长的路径了。这个我们怎么做呢？dfs？实际上是 dp 啦。
首先我们设 f_i 表示从 i 出发的最长路径的长度（注意这里的路径不成环，即不回到 i）。如果就此进行 dfs（即 dp），那么很显然不满足无后效性（即我们可以从一个环绕一圈后再回到当前点。不过别放弃，我们还有解决办法——我们预处理出 g_i 为从 i 出发后回到点 i 的最长路径。这样我们就可以借助 g_i 来维护 f_i 了。
那么如何维护 f_i,g_i？
考虑边 (i,j)，如果它不属于任何环，那么它对 g_i 一定没有贡献。这个很容易证明，就是过去了就没办法回来了，那么最后不可能可以回到起始点。
对于一条在环上的边 $(i,j)$，那么对于环，对 $g_i$ 的贡献为环的大小加上环上所有点 $x $ 的 $g_x$（虽然一条边只能属于一个环，但是没说一个点只能属于一个环呀）。对 $f_i$ 的贡献，就是先从 $i$ 走到环上的点 $x$（贡献为 $i,x$ 之间的距离），然后从 $x$ 往下走的贡献和（$f_x+g_x$）的最大值。
事实上，考虑上面的 dp 转移过程，我们付发现它和 Tarjan 的过程很像。所以我们直接把 dp 在 Tarjan 中进行即可。
---
知识点：dp，Tarjan，最长路径，圆方图，仙人掌图。（这里列举的是所有有关知识点，不一定全要用到）
```C++
#include<bits/stdc++.h>
#include <queue>
#define rep(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define per(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
#define int long long
#define pii pair<int,int>
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define rd read()
inline int read()
{
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int N=1e6+15;
const int INF=1e9+5;
const int MOD=998244353;
int n,m;
int nxt[N],h[N],to[N],tot;
int dfn[N],low[N],idx,fa[N],d[N];
int g[N],f[N];
void add(int a,int b){
nxt[++tot]=h[a],to[tot]=b,h[a]=tot;
}
void tarjan(int x){
int w=0;
dfn[x]=low[x]=++idx;
for(int i=h[x];i;i=nxt[i]){
int j=to[i];
if(j==fa[x])continue;
if(!dfn[j]){
d[j]=d[x]+1;fa[j]=x;tarjan(j);
low[x]=min(low[x],low[j]);
if(low[j]>dfn[x])w=max(w,f[j]+1);
}else{
low[x]=min(low[x],dfn[j]);
}
}
for(int i=h[x];i;i=nxt[i]){
int j=to[i],addg=1,addf=0;//后面两个是记录对g_i和f_i的贡献的临时变量
if(x==fa[j]||dfn[j]<=dfn[x])continue;
for(int k=j;k!=x;k=fa[k]){//回溯当前环
addf=max(addf,addg+f[k]);
addg+=g[k]+1;
}
g[x]+=addg;
for(int k=addg;j!=x;j=fa[j]){
k-=g[j]+1,addf=max(addf,k+f[j]);
w=max(w,addf-addg);
}
}
f[x]=g[x]+w;
}
signed main(){
n=rd,m=rd;
for(int i=1;i<=m;i++){
int a=rd,b=rd;
add(a,b);
add(b,a);
}
tarjan(1);
// for(int i=1;i<=n;i++)cerr<<f[i]<<' ';
cout<<f[1]<<endl;
}
```