某岛

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

BZOJ 1023. [SHOI2008]cactus仙人掌图

```const int N = int(5e4) + 9;
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) {
}
p = u;
}
}
nn = 0; dfs();
cout << z << endl;
}
}
```
```const int N = int(1e5) + 9;
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
}
} else if (dfn[v] < dfn[u]) { // Find Circle
checkMin(low[u], dfn[v]);
}
}
--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 {
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) {