仙人掌图直径

题：https://www.luogu.com.cn/problem/P4244

分析：定义f[i]表示dfs过程中 i 节点到子树叶子节点的最大距离；

　　　考虑俩种边的俩种情况，【1】假设枚举边为树边（桥），那么对答案的更新则为f[u]+f[v]+1,表示在枚举v之前的最大叶子节点距离和当前v节点到叶子节点的最大距离，同时用f[v]更新f[u].

　　　　　　　　　　　　　　【2】考虑环，环对答案的更新无非就选取俩个点i，j 的f[i]+f[j]+abs（i-j）。那么对于当前的i，只要找到最大的f[j]-j ，所以维护这样一个环的单调队列。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define MP make_pair
typedef long long ll;
const ll INF=1e18;
const int M=5e5+6;
int deep[M],a[M],fa[M],f[M],que[M],low[M],dfn[M];
vector<int>g[M];
int ans,cnt;
void solve(int u,int v){
    int sum=deep[v]-deep[u]+1;
    for(int i=v;i!=u;i=fa[i])
        a[sum--]=f[i];
    a[1]=f[u];
    sum=deep[v]-deep[u]+1;
    que[1]=1;
    int head=1,tail=1;
    for(int i=1;i<=sum;i++)
        a[i+sum]=a[i];
    for(int i=2;i<=sum+(sum>>1);i++){
        if(i-que[head]>(sum>>1))head++;///因为俩点间的距离是最短距离，所以把选的范围缩小为环的一半，这也是为什么要枚举3/2环
        ans=max(ans,a[i]+a[que[head]]+i-que[head]);///对于更新答案，a[i]+i是确定的，那么只要找到最大的a[j]-j即可，也就是维护a[j]-j的单调队列，保证头部是最大的
        while(head<=tail&&a[i]-i>=a[que[tail]]-que[tail])
            tail--;
        que[++tail]=i;
    }
    for(int i=2;i<=sum;i++)
        f[u]=max(f[u],a[i]+min(i-1,sum-i+1));///因为定义俩点最短距离为2，所以选取环的较短边。
}
void dfs(int u){
    dfn[u]=low[u]=++cnt;
    for(auto v:g[u]){
        if(v!=fa[u]){
            if(!dfn[v]){
                deep[v]=deep[u]+1;
                fa[v]=u;
                dfs(v);
            }
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
                ans=max(ans,f[u]+f[v]+1);
                f[u]=max(f[u],f[v]+1);
            }
        }
    }
    for(auto v:g[u]){
        if(fa[v]!=u&&dfn[v]>dfn[u])
            solve(u,v);
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    while(m--){
        int k,u=0,v;
        scanf("%d",&k);
        while(k--){
            scanf("%d",&v);
            if(u)g[u].pb(v),g[v].pb(u);
            u=v;
        }
    }
    dfs(1);
    printf("%d
",ans);
    return 0;
}