给定一个仙人掌图，求其直径。

题解

仙人掌什么的好难呀，看了好长时间的题解才理解究竟要怎么做，不过感觉还是蛮有趣的，处理树上和环上的方式也很巧妙，那么我就简单口胡一下。。

选一个点为根，DFS 整棵树，设 f(i) f(i) 表示DFS树中以节点 i i 为根的子树的点集在原图中的诱导子图中以 i i 开始的最长路径。

若不考虑环，记 Si S_i 为节点 i i 的儿子集合，则有 f(i)=maxj∈Si(f(j)+1) f(i) = \max\limits_{j \in S_i}(f(j) + 1) 。

然而由于环的存在，会使得某些点之间的距离变小，从而影响维护到的 f f 值的正确性，所以我们在转移 f(i) f(i) 时需要满足转移到他的节点 j j 不和 i i 处在同一个环上，即不在同一个环上转移 f f 。

判断环的问题，只需要在 DFS 的时候按照 Tarjan 算法的流程记录每个点的 low \text{low} 和 dfn \text{dfn} 即可。

由于仙人掌的特性，以及 DFS 的过程，对于每个环都可以找到一个深度最小的点，我们称这个点为 最高点，显然的，这个环的祖先的 f f 值的更新需要且仅需要用到最高点的 f f 值，所以对于整个环，在用环上的节点的不在环上的子节点更新过自身的 f f 后，只需要再更新最高点的 f f 值即可。

设最高点为 u u ，则 f(u) f(u) 由环上节点转移的方式为 f(u)=f(v)+dist(u,v) f(u) = f(v) + \text{dist}(u, v) ，其中 v v 和 u u 在同一环上，

以上内容全部是关于 f f 值的更新，接下来要说的是更新答案的方式。

对于桥上的答案，我们在 DFS 过程中更新 f f 值的同时更新答案，设答案为 ans \text{ans} ，目前正在更新 f f 值的节点为 i i ，则此时有 ans=f(i)+f(j)+1,j∈Si \text{ans} = f(i) + f(j) + 1, j \in S_i 。注意要在尝试从节点 j j 转移 f f 值之前更新答案，否则不能涵盖所有情况，还可能导致状态出现错误。

显然地，环上的节点也可以用来更新答案。对于环上的节点 i,j i, j 来说，其导致的答案的形式应该是 f(i)+f(j)+dist(i,j) f(i) + f(j) + \text{dist}(i, j) 。设 s(i) s(i) 为节点 i i 在环上的编号（编号按照 DFS树 上的深度为顺序），则原式可以改写成为 f(i)+f(j)+∣s(i)−s(j)∣ f(i) + f(j) + |s(i) - s(j)| 。如果按照深度为顺序转移答案，并且保证在枚举到节点 i i 时转移区间连续并且长度不超过环长度的一半，就可以使用单调队列维护 f(j)−s(j) f(j) - s(j) 的值来优化转移。

具体细节详见代码。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <stack>
#include <algorithm>
const int MAX_N = 50000;
struct Node;
struct Edge;
struct Node {
    Edge *e;
    Node *fa;
    int dfn, low;
    int len;
    bool vis;
} N[MAX_N + 1];
struct Edge {
    Node *fr, *to;
    Edge *ne;
    Edge(Node *fr, Node *to) : fr(fr), to(to), ne(fr->e) {}
};
inline void addEdge(int fr, int to) {
    N[fr].e = new Edge(&N[fr], &N[to]);
    N[to].e = new Edge(&N[to], &N[fr]);
}
inline void circle(Node *top, Node *u, int &ans) {
    static Node *v[MAX_N * 2];
    int cnt = 0;
    while (true) {
        v[cnt++] = u;
        if (u == top) break;
        u = u->fa;
    }
    std::reverse(v, v + cnt);
    std::copy(v, v + cnt, v + cnt);
    int half = cnt / 2;
    static int q[MAX_N * 2];
    int *l = q, *r = q;
    *r = 0;
    for (int i = 1; i < cnt * 2; i++) {
        while (i - *l > half) l++;
        ans = std::max(ans, v[*l]->len + v[i]->len + i - *l);
        while (l <= r && v[i]->len - i > v[*r]->len - *r) r--;
        *++r = i;
    }
    int res = 0;
    for (int i = 1; i < cnt; i++) {
        res = std::max(res, v[i]->len + std::min(i, cnt - i));
    }
    top->len = std::max(top->len, res);
}
int ans = 0;
void tarjan(Node *v) {
    static int ts = 0;
    v->dfn = v->low = ++ts;
    for (Edge *e = v->e; e; e = e->ne) {
        if (e->to != v->fa) {
            if (!e->to->dfn) {
                e->to->fa = v;
                tarjan(e->to);
                v->low = std::min(v->low, e->to->low);
            } else v->low = std::min(v->low, e->to->dfn);
            if (v->dfn < e->to->low) {
                ans = std::max(ans, v->len + e->to->len + 1);
                v->len = std::max(v->len, e->to->len + 1);
            }
        }
    }
    for (Edge *e = v->e; e; e = e->ne) {
        if (e->to->fa != v && e->to->dfn > v->dfn) {
            circle(v, e->to, ans);
        }
    }
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int k, u;
        scanf("%d %d", &k, &u);
        for (int j = 2; j <= k; j++) {
            int v;
            scanf("%d", &v);
            addEdge(u, v);
            u = v;
        }
    }
    tarjan(&N[1]);
    printf("%d\n", ans);
    return 0;
}