https://www.lydsy.com/JudgeOnline/problem.php?id=1023

题意：求仙人掌图的直径（最远两点的最短距离）。

同样，首先考虑树的直径求法。

dp[i]dp[i] 表示以 ii 为根的子树中点与 ii 的最远距离。

ansans 表示树的直径。

dp[u]=max(dp[v]+1,(u,v)∈E)dp[u]=max(dp[v]+1,(u,v)\in E)

ans=max(dp[u]+dp[v]+1,(u,v)∈E)ans=max(dp[u]+dp[v]+1,(u,v)\in E)

根据套路，还是把环单独拿出来处理。

考虑怎么扫一遍环求出所有与环上点有关的直径。

对于环上两点 u,vu,v，经过这两点的最长路径为

dp[u]+dis[u][v]+dp[v]=dp[u]+dp[v]+min(abs(depth[v]−dep[u]),C−abs(depth[v]−depth[u]))dp[u]+dis[u] [v]+dp[v]\\=dp[u]+dp[v]+min(abs(depth[v]-dep[u]),C-abs(depth[v]-depth[u]))

有绝对值存在不好处理，所以把环展开，复制两倍。

这样可以始终保持队列头和尾的深度差不超过环的长度的一半。

dp[u]+dis[u][v]+dp[v]=dp[u]+dp[v]+depth[u]−depth[v]=dp[u]+depth[u]+(dp[v]−depth[v])dp[u]+dis[u] [v]+dp[v] \\=dp[u]+dp[v]+depth[u]-depth[v] \\=dp[u]+depth[u]+(dp[v]-depth[v])

通过上式最后一步的转化，又可以把经过点 uu 与其它点的直径长度转化为可以用单调队列求的问题。随着深度递增，保持队列中点的 dp[v]−depth[v]dp[v]-depth[v] 递减，这样每次有一个新点u，只要队首有效，则经过u的最长直径一定是由队首更新的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
int n, m;
vector<int>G[maxn];
int dp[maxn];
int dfn[maxn],fa[maxn],low[maxn];
int dep[maxn];
int cnt;
int a[maxn],q[maxn];
int ans;
void solve(int u,int v){
    int top=dep[v]-dep[u]+1;
    for(int i=v;i!=u;i=fa[i])a[top--]=dp[i];
    a[1]=dp[u];
    top=dep[v]-dep[u]+1;
    for(int i=1;i<=top;i++)a[i+top]=a[i];
    int l=1,r=1;
    q[r]=1;
    for(int i=2;i<=2*top;i++){
        while(l<=r&&i-q[l]>top/2)l++;
        ans=max(ans,a[q[l]]+a[i]+i-q[l]);
        while(l<=r&&a[q[r]]-q[r]<=a[i]-i)r--;
        q[++r]=i;
    }
    for(int i=2;i<=top;i++)dp[u]=max(dp[u],a[i]+min(top-i+1,i-1));
}
void dfs(int u,int _fa){
    dfn[u]=low[u]=++cnt;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==_fa)continue;
        if(!dfn[v]){
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs(v,u);
            low[u]=min(low[u],low[v]);
        }
        else{
            low[u]=min(low[u],dfn[v]);
        }
        if(dfn[u]<low[v]){
            ans=max(ans,dp[u]+dp[v]+1);
            dp[u]=max(dp[u],dp[v]+1);
        }
    }
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==_fa)continue;
        if(fa[v]!=u&&dfn[u]<dfn[v]){
            solve(u,v);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int k;
        scanf("%d",&k);
        int a,b;
        scanf("%d",&a);
        for(int i=1;i<k;i++){
            scanf("%d",&b);
            G[a].push_back(b);
            G[b].push_back(a);
            a=b;
        }
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}