[SHOI2008]仙人掌图 II题解

发表于 2021-10-21

[SHOI2008]仙人掌图II

思路

遇到仙人掌一般都会想到圆方树，然而这道题用不到。

考虑没有环的情况, 那就是树的直径了。

这道题是有环的，但是发现只有两个点都在环上时不能直接用求树的直径的方法转移。

设 $f_i$ ，对于环上的点表示除非 $i$ 是当前环的根，否则 $i$ 不能经过环上的其它点，所能到达的最深的点。

对于不在环上的点，定义和树一样。

点的深度定义为到根节点的最短距离，环的根指这个环最先被 $dfs$ 到的点。

那么当两个点都在环上时应该怎么转移呢？

根据 $f_i$ 的定义只有根可以从其它环上的点转移过来，从根的一个儿子开始绕环一圈并标号，设 $cnt$ 表示环的大小, $a[i]$ 表示环上标号为 $i$ 的点, 则 $f[a[cnt]] = \max_{i=1}^{cnt - 1}f[a[i]] + \min(cnt - i, i)$

然后就是如何统计跨环的链对于答案的影响。

先断环成链，然后枚举下标 $i$ , $j$ 使 $j < i$ 且 $j \leq i - cnt / 2$ 因为 $i,j$ 会选择较短的链.

$ans' = \max(ans, f[a[i]] + f[a[j]] + i - j)$ 这个东西可以用单调队列优化.

最后复杂度是 $O(n)$ 的。

Code

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 2e7 + 10;
int n, m;
int head[N], nxt[M], to[M], e_tot = 1;
int dfn[N], low[N], fa[N], tim;
int f[2 * N], a[2 * N], cnt;
int q[4 * N], h, t;
int ans;

void add(int x, int y)
{
  nxt[++e_tot] = head[x], head[x] = e_tot, to[e_tot] = y;
}

void calc(int u, int v)
{
  int x = v;
  cnt = 0, h = 1, t = 0;
  while (x != u)
  {
    a[++cnt] = x, x = fa[x];
  }
  a[++cnt] = u;
  for (int i = 1; i <= cnt; ++i) a[i + cnt] = a[i];
  for (int i = 1; i <= 2 * cnt; ++i)
  {
    if (h <= t && q[h] < i - cnt / 2) ++h;
    while (h <= t && f[a[q[t]]] - q[t] < f[a[i - 1]] - (i - 1)) --t;
    q[++t] = i - 1;
    ans = max(ans, f[a[i]] + i + f[a[q[h]]] - q[h]);
  }
  for (int i = 1; i < cnt; ++i)
  {
    f[u] = max(f[u], f[a[i]] + min(i, cnt - i));
  }
}

void tarjan(int u, int _fa)
{
  dfn[u] = low[u] = ++tim;
  for (int i = head[u]; i; i = nxt[i])
  {
    int v = to[i];
    if (v == _fa) continue;
    if (!dfn[v])
    {
      fa[v] = u;
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
    }
    else low[u] = min(low[u], dfn[v]);
    if (low[v] > dfn[u])
    {
      ans = max(ans, f[u] + f[v] + 1);
      f[u] = max(f[u], f[v] + 1);
    }
  }
  for (int i = head[u]; i; i = nxt[i])
  {
     int v = to[i];
     if (fa[v] != u && dfn[v] > dfn[u]) calc(u, v);
  }
}


int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i)
  {
    int k;
    scanf("%d", &k);
    for (int i = 1; i <= k; ++i)
    {
      scanf("%d", &a[i]);
    }
    for (int i = 2; i <= k; ++i)
    {
      add(a[i], a[i - 1]);
      add(a[i - 1], a[i]);
    }
  }
  tarjan(1, 0);
  cout << ans << endl;
  return 0;
}

[SHOI2008]仙人掌图II

标签

思路

Code