LinkDescription马老师要你求一棵仙人掌的直径，边权为 $1$。Sol在普通的树上直接 DP 即可. 现在考虑建出圆方树后, 在环上的特别处理对于方点，相当于我们要求必须经过环的一颗基环树的直径。也就是求$max\{f_i + f_j + dis(i,j)\}$，这个可以将环倍长用一个单调队列做。具体地, 用单调队列维护最大值，若当前位置 $i$ 和队首 $j$ 距离超过 $\frac{len}{2}$ 时,就弹出队首.Code我感觉代码其实还算好写#include <bits/stdc++.h> using namespace std; typedef std::vector < int > vec; const int SIZE = 1e5 + 5, SIZE_M = 5e6 + 5; const int inf = 2e9; int n, N, m, num, tim, ans; int head[SIZE], fa[SIZE], dfn[SIZE], cir[SIZE], f[SIZE], cha[SIZE], q[SIZE]; vec g[SIZE]; struct node { int to, nxt; } edge[SIZE_M << 1]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; void addEdge(int u, int v) { edge[++ num] = (node) {v, head[u]}, head[u] = num; } void dfs(int u) { dfn[u] = ++ tim; for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (v == fa[u]) continue; if (!dfn[v]) { cir[u] = 0, fa[v] = u; dfs(v); if (!cir[u]) g[u].emplace_back(v), g[v].emplace_back(u); } else if (dfn[v] < dfn[u]) { int x = u; ++ N; g[x].emplace_back(N), g[N].emplace_back(x); do { x = fa[x]; g[x].emplace_back(N), g[N].emplace_back(x); cir[x] = 1; } while (x != v); } } } void dp(int u, int anc) { for (auto v: g[u]) { if (v != anc) dp(v, u); } if (u <= n) { int mx = 0; for (auto v: g[u]) { if (v == anc) continue; mx = std::max(mx, f[v] + 1); if (mx > f[u]) std::swap(f[u], mx); } ans = std::max(f[u] + mx, ans); } else { int head = 1, tail = 0, cnt = 0; for (auto v: g[u]) { if (v == anc) continue; cha[++ cnt] = v; } for (int i = 1; i <= cnt; ++ i) cha[i + cnt] = cha[i]; for (int i = 1; i <= cnt * 2; ++ i) { while (head <= tail && (i - q[head]) > (cnt + 1) / 2) ++ head; if (i >= cnt) ans = std::max(ans, f[cha[q[head]]] + f[cha[i]] + i - q[head]); while (head <= tail && f[cha[i]] - i >= f[cha[q[tail]]] - q[tail]) -- tail; q[++ tail] = i; } for (int i = 1; i <= cnt / 2; ++ i) f[u] = std::max(f[u], f[cha[i]] + i - 1); for (int i = cnt / 2 + 1; i <= cnt; ++ i) f[u] = std::max(f[u], f[cha[i]] + cnt - i); } } int main() { n = N = read(), m = read(); for (int i = 1, tot, u, v; i <= m; ++ i) { tot = read(), u = v = 0; for (int j = 1; j <= tot; ++ j) { v = read(); if (u) { addEdge(u, v); addEdge(v, u); } u = v; } } dfs(1); dp(1, 0); printf("%d\n", ans); return 0; }