某島

… : "…アッカリ~ン . .. . " .. .
March 11, 2020

BZOJ 1023. [SHOI2008]cactus仙人掌圖


https://www.cnblogs.com/onioncyc/p/8308835.html
https://blog.csdn.net/LPA20020220/article/details/88887945
https://cmxrynp.github.io/2018/11/01/BZOJ-1023-SHOI2008-cactus%E4%BB%99%E4%BA%BA%E6%8E%8C%E5%9B%BE/

const int N = int(5e4) + 9;
VI adj[N]; int fa[N];
int dfn[N], low[N], nn;
int f[N]; // 子樹中的最遠距離
int n, p, z;

int q[2*N], cz, op;
void gao(int st, int ed) {
    VI C; int u; for (u=st;u!=ed;u=fa[u]) C.PB(f[u]);
    int ff = 0; REP(i, SZ(C)) checkMax(ff, C[i] + min(i, SZ(C)-1-i));
    checkMax(z, f[u] + ff); C.PB(f[u]); checkMax(f[u], ff);
    int n = SZ(C)/2;

    REP(i, n) C.PB(C[i]);
    int cz = 0, op = 0; q[0] = 0; FOR(i, 1, SZ(C)) {
        if (i - q[cz] > n) ++cz;
        checkMax(z, C[i] + C[q[cz]] + i - q[cz] - 2);
        while (cz <= op && C[q[op]] - q[op] <= C[i] - i) --op;
        q[++op] = i;
    }
}

void dfs(int u = 0) {
#define v (*it)
    low[u] = dfn[u] = ++nn;

    ECH(it, adj[u]) if (v != fa[u]) {
        if (!dfn[v]) {
            fa[v] = u; dfs(v);
            checkMin(low[u], low[v]);
        } else {
            checkMin(low[u], dfn[v]);
        }
        if (dfn[u] < low[v]) {
            checkMax(z, f[u] + f[v]);
            checkMax(f[u], f[v]);
        } else if (fa[v] != u && dfn[u] < dfn[v]) {
            gao(v, u);
        }
    }
    f[u] += 1;
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d", &n)) {

        REP(i, n) f[i] = fa[i] = 0, adj[i].clear();

        Rush {
            int p = -1; Rush {
                int u; RD(u); --u;
                if (~p) {
                    adj[p].PB(u);
                    adj[u].PB(p);
                }
                p = u;
            }
        }
        nn = 0; dfs();
        cout << z << endl;
    }
}
const int N = int(1e5) + 9;
VI adj[N], adjj[N]; int fa[N];
int dfn[N], low[N], tt, sta[N], top;
int f[N]; // 子樹中的最遠距離
int n, nn, z;

#define v (*it)
void tarjan(int u = 0) {

    low[u] = dfn[u] = ++tt;
    sta[++top] = u;

    ECH(it, adj[u]) if (v != fa[u]) {
        if (!dfn[v]) {
            fa[v] = u; tarjan(v);
            checkMin(low[u], low[v]);
            if (dfn[v] == low[v]) {  // is Tree Edge
                adjj[u].PB(v);
            }
        } else if (dfn[v] < dfn[u]) { // Find Circle
            checkMin(low[u], dfn[v]);
            adjj[v].PB(++nn); fa[nn] = n;
            for (int i=top;sta[i]!=v;--i) adjj[nn].PB(sta[i]);
        }
    }
    --top;
}

int q[2*N], cz, op; VI C;
void dfs(int u = 0) {
    if (u < n) {
        ECH(it, adjj[u]) if (v != fa[u]) {
            dfs(v);
            checkMax(z, f[u] + f[v] + 1);
            checkMax(f[u], f[v] + 1);
        }
    } else {
        ECH(it, adjj[u]) dfs(v);
        C.clear(); ECH(it, adjj[u]) C.PB(f[v]);
        REP(i, SZ(C)) checkMax(f[u], C[i] + min(i, SZ(C)-1-i));
        C.PB(-INF); int n = SZ(C)/2; REP(i, n) C.PB(C[i]);
        int cz = 0, op = 0; q[0] = 0; FOR(i, 1, SZ(C)) {
            if (i - q[cz] > n) ++cz;
            checkMax(z, C[i] + C[q[cz]] + i - q[cz]);
            while (cz <= op && C[q[op]] - q[op] <= C[i] - i) --op;
            q[++op] = i;
        }
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d", &n)) {

        REP(i, n) f[i] = 0, adj[i].clear();

        Rush {
            int p = -1; Rush {
                int u; RD(u); --u;
                if (~p) {
                    adj[p].PB(u);
                    adj[u].PB(p);
                }
                p = u;
            }
        }
        top = tt = 0; nn = n-1; tarjan(); dfs();
        cout << z << endl;
    }
}