这道题是我做的第一道仙人掌DP，小小纪念一下……
仙人掌DP就是环上的点环状DP，树上的点树上DP。就是说，做一遍DFS，DFS的过程中处理出环，环上的点先不DP，先把这些换上的点的后继点都处理出来，再从环上DFS序最小的点开始进行环状DP，就ok了。但是注意判断是不是父边不能用 v[k] != fa[now]，这样如果两个点构成一个环就会出错，所以存这个点的父边，记为fb[now]，这样判断的时候只需判断(k^1) != fb[now]，就可以了。在环状DP的时候我想了很久怎么用单调队列优化（其实是我太弱了，环状DP都不会写=_=）。存一个p[i] = f[i]-i，然后用 f[i]+i+p[j] 更新答案就可以了，最后只需更新环最顶端的点的 f 值而不用全部修改。
这么说很笼统，还是看代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <stack>
#define N 500100
#define M 1001000
using namespace std; int n, m;
int p[N], next[M], v[M], bnum = -;
int f[N] = {};
int ans = ; void addbian(int x, int y)
{
bnum++; next[bnum] = p[x]; p[x] = bnum; v[bnum] = y;
bnum++; next[bnum] = p[y]; p[y] = bnum; v[bnum] = x;
} int nowtime = ;
int low[N], vist[N] = {}, fb[N], fa[N];
bool instack[N] = {}; int roop[N], roopnum; struct ss
{
int place, val;
}dui[N];
int head, tail; void work_circle()
{
int limit = roopnum/;
for (int i = roopnum+; i <= (roopnum<<); ++i) roop[i] = roop[i-roopnum];
ss x; x.val = f[roop[]]-; x.place = ;
head = ; tail = ; dui[head] = x;
for (int i = ; i <= (roopnum<<); ++i)
{
while (dui[head].place+limit < i) head++;
ans = max(ans, f[roop[i]]+i+dui[head].val);
x.val = f[roop[i]]-i; x.place = i;
while (dui[tail].val < x.val && tail >= head) tail--;
dui[++tail] = x;
}
} void dfs(int now)
{
int k = p[now]; vist[now] = ++nowtime; low[now] = vist[now];
while (k != -)
{
if (k != fb[now])
{
if (vist[v[k]]) low[now] = min(low[now], vist[v[k]]);
else
{
fa[v[k]] = now; fb[v[k]] = k^;
dfs(v[k]);
low[now] = min(low[now], low[v[k]]);
}
}
k = next[k];
}
k = p[now];
while (k != -)
{
if ((k^) == fb[v[k]] && low[v[k]] > vist[now])
{
ans = max(ans, f[now] + f[v[k]] + );
f[now] = max(f[now], f[v[k]] + );
}
if ((k^) != fb[v[k]] && vist[now] < vist[v[k]])
{
roopnum = ;
int x = v[k];
while (x != fa[now])
{
roop[++roopnum] = x;
x = fa[x];
}
work_circle();
for (int i = ; i < roopnum; ++i)
f[now] = max(f[now], f[roop[i]]+min(i, roopnum-i));
}
k = next[k];
}
} int main()
{
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i) p[i] = -;
for (int i = ; i <= m; ++i)
{
int k, x, y; scanf("%d%d", &k, &x);
for (int j = ; j < k; ++j)
{
scanf("%d", &y);
addbian(x, y);
x = y;
}
}
fa[] = ; fb[] = -; dfs();
printf("%d\n", ans);
return ;
}