[SHOI2008]仙人掌图

还不会仙人掌的同学可以看看我对仙人掌知识的一些梳理。

题意就是求仙人掌的直径，直径定义为图中最短路径最长的两点间的最短路径长度。

按照套路，先考虑求树的直径我们是怎么做的。设\(f[i]\)表示\(i\)往下最长链的长度，\(j\)是\(i\)的儿子，转移和更新答案就是（我习惯用\(o\)表示答案）：

\[f[i] = max\{f[j]\} + 1 \qquad o = max\{f[i] + f[j] + 1\}
\]

考虑放到仙人掌上，对于树边直接转移和更新答案；对于非树边，先把环拎出来，可以直接转移，设\(i\)是环顶端的点，\(j\)是环上的其他点，\(k\)是环的大小：

\[f[i] = max\{f[j] + dis(i, j)\}
\]

\(dis(i, j)\)可以用深度差和环大小减深度差的较小值来表示。

更新答案似乎不能直接搞，考虑断环为链，维护个单调队列：如果队首元素超过环大小的一半就出队，用准备进队的元素和队首元素更新答案，如果当前进队元素的\(f\)减去队尾元素的\(f\)大于等于他们在环上的距离就弹出队尾懒得放数学公式了，可以结合代码理解。

#include <cstdio>

#include <cctype>

#include <vector>

#include <algorithm>

#define R register

#define I inline

#define B 1000000

using namespace std;

const int N = 50003, M = 100003;

char buf[B], *p1, *p2;

I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++; }

I int rd() {

    R int f = 0;

    R char c = gc();

    while (c < 48 || c > 57)

        c = gc();

    while (c > 47 && c < 58)

        f = f * 10 + (c ^ 48), c = gc();

    return f;

}

int s[N], p[N], d[N], l[N], e[M], q[M], f[N], t, o;

vector <int> g[N];

I int min(int x, int y) { return x < y ? x : y; }

I int max(int x, int y) { return x > y ? x : y; }

void dfs(int x, int h) {

    p[x] = h, d[x] = l[x] = ++t;

    R int i, y;

    for (i = 0; i < s[x]; ++i) {

        if (!d[y = g[x][i]])

            dfs(y, x), l[x] = min(l[x], l[y]);

        else

            if (y ^ h)

                l[x] = min(l[x], d[y]);

        if (l[y] > d[x])

            o = max(o, f[x] + f[y] + 1), f[x] = max(f[x], f[y] + 1);

    }

    for (i = 0; i < s[x]; ++i)

        if (p[y = g[x][i]] ^ x && d[x] < d[y]) {

            R int j, k = 0, u = 1, v = 0;

            for (j = y; j ^ x; j = p[j])

                e[++k] = f[j];

            e[++k] = f[x], reverse(e + 1, e + k + 1);

            for (j = 1; j <= k; ++j)

                e[j + k] = e[j];

            k <<= 1, q[++v] = 1;

            for (j = 2; j <= k; q[++v] = j, ++j) {

                while (j - q[u] > (k >> 2) && u <= v)

                    ++u;

                if (u <= v)

                    o = max(o, e[j] + e[q[u]] + j - q[u]);

                while (e[j] - e[q[v]] >= j - q[v] && u <= v)

                    --v;

            }

            k >>= 1;

            for (j = 2; j <= k; ++j)

                f[x] = max(f[x], e[j] + min(j - 1, k - j + 1));

        }

}

int main() {

    R int n = rd(), m = rd(), i, j, k, x, y;

    for (i = 1; i <= m; ++i) {

        k = rd(), x = rd();

        for (j = 1; j < k; x = y, ++j)

            y = rd(), g[x].push_back(y), g[y].push_back(x);

    }

    for (i = 1; i <= n; ++i)

        s[i] = g[i].size();

    dfs(1, 0), printf("%d", o);

    return 0;

}

巴特西

[SHOI2008]仙人掌图

[SHOI2008]仙人掌图

最新文章

热门文章