给出一种仅使用单调队列优化 DP 和 Tarjan 点双联通分量的做法。
具体上,在 Tarjan 时维护每个点离子树中点的最远距离。
找到环之后用单调队列维护环里的最大值。
#include <iostream>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 400010, M = N << 3;
int n, m, res;
int h[N], nh[N], e[M], ne[M], idx;
int low[N], dfn[N], time_stamp;
int w[N], f[N], q[N], fa[N];
inline void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void calc(int root, int u)
{
int cnt = 0;
for (int i = u; i != fa[root]; i = fa[i])
w[ ++ cnt] = f[i];
int hh = 0, tt = 0;
q[0] = cnt * 2;
for (int i = 1; i <= cnt; i ++ ) w[i + cnt] = w[i];
for (int i = cnt * 2 - 1; i >= 1; i -- )
{
while (hh <= tt && q[hh] - i > cnt / 2) hh ++ ;
res = max(res, w[i] + w[q[hh]] + q[hh] - i);
while (hh <= tt && w[q[tt]] + q[tt] <= w[i] + i) tt -- ;
q[ ++ tt] = i;
}
for (int i = 1; i < cnt; i ++ )
f[root] = max(f[root], w[i] + min(i, cnt - i));
}
void tarjan(int u, int father)
{
dfn[u] = low[u] = ++ time_stamp;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == father) continue;
if (!dfn[j])
{
fa[j] = u;
tarjan(j, u);
low[u] = min(low[u], low[j]);
}
else low[u] = min(low[u], dfn[j]);
if (low[j] > dfn[u])
{
res = max(res, f[u] + f[j] + 1);
f[u] = max(f[u], f[j] + 1);
}
}
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (fa[j] != u && dfn[j] > dfn[u])
calc(u, j);
}
}
int main()
{
int a, b, c;
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m -- )
{
scanf("%d%d", &a, &b);
for (int i = 1; i < a; i ++ )
scanf("%d", &c), add(b, c), add(c, b), b = c;
}
tarjan(1, -1);
printf("%d\n", res);
return 0;
}