某岛

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

BZOJ 4316. 小C的独立集

```const int N = int(5e4) + 9;
int dfn[N], low[N], nn;
int f0[N], f1[N]; // 不取, 取 or 不取
int n, p;

void gao(int st, int ed) {
int u,t,g0,g1;

g0 = f0[st]; g1 = f0[st]; u = fa[st];
while (u != ed) {
int gg = g0;
g0 = g1 + f0[u];
g1 = gg + f1[u];
checkMax(g1, g0);
u = fa[u];
}
f1[u] += g0;

g0 = f0[st]; g1 = f1[st]; u = fa[st];
while (u != ed) {
int gg = g0;
g0 = g1 + f0[u];
g1 = gg + f1[u];
checkMax(g1, g0);
u = fa[u];
}
checkMax(g1, g0);
f0[u] += g1;
}

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]) {
f0[u] += f1[v];
f1[u] += f0[v];
} else if (fa[v] != u && dfn[u] < dfn[v]) {
gao(v, u);
}
}
f1[u] += 1;
checkMax(f1[u], f0[u]);
}

int main() {

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

RD(n); Rush {
int x, y; RD(x, y); --x, --y;