「BZOJ1023」[SHOI2008]cactus仙人掌图

Description

如果某个无向连通图的任意一条边至多只出现在一条简单回路（simple cycle）里，我们就称这张图为仙人掌
图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。

举例来说,上面的第一个例子是一张仙人图,而第二个不是——注意到它有三条简单回路：、以及,而同时出现在前两个的简单回路里。另外,第三张图也不是仙人图,因为它并不是连通图。显然,仙人图上的每条边,或者是这张仙人图的桥(bridge),或者在且仅在一个简单回路里,两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。现在我们假定仙人图的每条边的权值都是1,你的任务是求出给定的仙人图的直径。

Input

输入的第一行包括两个整数和以及。其中代表顶点个数，我们约定图中的顶
点将从到编号。接下来一共有行。代表m条路径。每行的开始有一个整数，代表在这条路径上
的顶点个数。接下来是个到之间的整数，分别对应了一个顶点，相邻的顶点表示存在一条连接这两个顶点的边
。一条路径上可能通过一个顶点好几次，比如对于第一个样例，第一条路径从经过，又从返回到了，但是我们
保证所有的边都会出现在某条路径上，而且不会重复出现在两条路径上，或者在一条路径上出现两次。

Output

只需输出一个数，这个数表示仙人图的直径长度。

Sample Input

15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10    8
10 1
10 1 2 3 4 5 6 7 8 9 10

Sample Output

8
9

HINT

对第一个样例的说明：如图，号点和号点的最短路径长度为，所以这张图的直径为。

Solution

环和链分别考虑。
链直接
环上是由两个点合并过来的， 为到在环上的距离。
环上按照顺序，从到枚举一下，然后对于每一个枚举的，求最大
对于前面的点，都是同时单调递增，只要维护最大值。注意队列里要保证最大距离是小于半环的。
为了方便，环拆成两倍，破环成链。
我直接无脑建立圆方树，然后直接算直径，错了。zz

这个数据就不行了。
方点是，那么如果和直接算，直接萎了，因为要知道环上距离呀。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 51000 * 2, M = 510000;
int n, m, tot;
int ans;
struct G2 {
    struct Edge {
        int u, v, nxt, w;
    }e[M * 2];
    int head[N], en;
    void addedge(int x, int y, int z) {
        e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
        e[en].w = z;
    }
    int f[N], g[N];
    void dfs(int x, int F) {
        for(int i = head[x]; i; i = e[i].nxt) {
            int y = e[i].v;
            if(y == F) continue;
            dfs(y, x);
            if(f[y] + e[i].w > f[x]) g[x] = f[x], f[x] = f[y] + e[i].w;
            else if(f[y] + e[i].w > g[x]) g[x] = f[y] + e[i].w;
        }
        ans = max(ans, f[x] + g[x]);
    }
}g2;
struct G1 {
    struct Edge {
        int u, v, nxt;
    }e[M * 2];
    int head[N], en;
    void addedge(int x, int y) {
        e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
    }
    int dfn[N], low[N], num;
    int fa[N];
    int sum[N];
    void solve(int x, int F) {
        ++tot;
        sum[tot] = 1;
        int i = x;
        while(i != F) {
            sum[i] = sum[tot];
            ++sum[tot];
            i = fa[i];
        }
        i = x;
        while(i != F) {
            int val = min(sum[i], sum[tot] - sum[i]);
            g2.addedge(tot, i, val);
            g2.addedge(i, tot, val);
            i = fa[i];
        }
        g2.addedge(tot, F, 0);
        g2.addedge(F, tot, 0);
    }
    void tarjan(int x, int F) {
        dfn[x] = low[x] = ++num;
        for(int i = head[x]; i;i = e[i].nxt) {
            int y = e[i].v;
            if(y == F) continue;
            if(!dfn[y]) {
                fa[y] = x;
                tarjan(y, x);
                low[x] = min(low[x], low[y]);    
            } else low[x] = min(low[x], dfn[y]);
            if(low[y] <= dfn[x]) continue;
            g2.addedge(x, y, 1);
            g2.addedge(y, x, 1);
        }
        for(int i = head[x]; i;i = e[i].nxt) {
            int y = e[i].v;
            if(fa[y] == x || low[y] != dfn[x]) continue;
            solve(y, x);
        }
    }
}g1;

int main() {
    n = read(), m = read(),tot = n;
    for(int i = 1; i <= m; ++i) {
        int k = read();
        int pre;
        for(int j = 1;  j<= k; ++j) {
            int x = read();
            if(j > 1) g1.addedge(pre, x), g1.addedge(x, pre);
            pre = x;
        }
    }
    g1.tarjan(1, 0);
    g2.dfs(1, 0);
    writeln(ans);
    return 0;
}

std

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 51000 * 2, M = 510000;
int n, m;
int ans;
int f[N];
struct G1 {
    struct Edge {
        int u, v, nxt;
    }e[M * 2];
    int head[N], en;
    void addedge(int x, int y) {
        e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
    }
    int dfn[N], low[N], num;
    int fa[N], tot, a[N*2];
    int q[N*2], h, t;
    void solve(int x, int F) {
        tot = 0;
        for(int i = x; i != fa[F]; i = fa[i]) a[++tot] = i;
        for(int i = 1; i <= tot; ++i) a[i + tot] = a[i];
        q[h = t = 1] = 1;
        f[0] = -1e9;
        for(int i = 2; i <= tot * 2; ++i) {
             while(h <= t && i - q[h] > tot / 2) ++h;
            ans = max(ans, f[a[i]] + f[a[q[h]]] + i - q[h]);
             while(h <= t && f[a[i]] >= f[a[q[t]]] + i - q[t]) --t;
             q[++t] = i;
         }
        for(int i = 1; i <= tot; ++i) f[F] = max(f[F], f[a[i]] + min(tot - i, i));
        ans = max(ans, f[F]);
    }
    void tarjan(int x, int F) {
        dfn[x] = low[x] = ++num;
        for(int i = head[x]; i;i = e[i].nxt) {
            int y = e[i].v;
            if(y == F) continue;
            if(!dfn[y]) {
                fa[y] = x;
                tarjan(y, x);
                low[x] = min(low[x], low[y]);    
            } else low[x] = min(low[x], dfn[y]);
            if(low[y] <= dfn[x]) continue;
            ans = max(ans, f[x] + f[y] + 1);
            f[x] = max(f[x], f[y] + 1);
            ans = max(ans, f[x]);
        }
        for(int i = head[x]; i;i = e[i].nxt) {
            int y = e[i].v;
            if(fa[y] == x || low[y] != dfn[x]) continue;
            solve(y, x);
        }
    }
}g1;

int main() {
    n = read(), m = read();
    for(int i = 1; i <= m; ++i) {
        int k = read();
        int pre;
        for(int j = 1;  j<= k; ++j) {
            int x = read();
            if(j > 1) g1.addedge(pre, x), g1.addedge(x, pre);
            pre = x;
        }
    }
    g1.tarjan(1, 0);
    writeln(ans);
    return 0;
}