Bzoj 1123
题意：Byteotia城市有$n$个towns, $m$条双向roads. 每条road连接 两个不同的towns ,没有重复的road. 所有towns连通。输出$n$个数，代表如果把第$i$个点去掉，将有多少对点不能互通，点对有序。
求出割点，然后对每个割点进行计数，显然如果删去割点，原图变为几个连通块，对于每个联通块都与不在这个连通块的元素不连通，所以求出第一部分的解。然后因为割点父亲的联通块无法通过割点来判，那么减一下算就行。最后割点本身还有算，加上$n-1$
对于不是割点的，答案为$2(n-1)$
1、Tarjan 不要将 low dfn 写在外面
2、计数题如果说了有序可以想想怎样有序做，不一定非要先求无序再求有序。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
struct edge {
int v, nxt;
} ed[1000000 + 5];
int n, m, en, hd[MAXN], sz, dfn[MAXN], low[MAXN], siz[MAXN], iscut[MAXN];
LL ans[MAXN];
void ins(int u, int v) {ed[++en] = (edge){v, hd[u]}, hd[u] = en;}
void tarjan(int u, int fa) {
int child = 0;
dfn[u] = low[u] = ++sz, siz[u] = 1;
LL sum = 0ll;
for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != fa) {
if (!dfn[e.v]) {
tarjan(e.v, u);
++child;
if (low[e.v] >= dfn[u])
iscut[u] = 1, ans[u] += 1ll * (n - siz[e.v]) * siz[e.v], sum += siz[e.v];
low[u] = min(low[u], low[e.v]);
siz[u] += siz[e.v];
} else low[u] = min(low[u], dfn[e.v]);
}
}
if (fa == 0 && child <= 1) iscut[u] = 0;
ans[u] += n - 1ll;
ans[u] += 1ll * (sum + 1ll) * (n - sum - 1ll);
if (!iscut[u]) ans[u] = 2ll * (n - 1ll);
}
void clean() {
ms(hd, -1), en = -1, sz = 0;
ms(dfn, 0), ms(low, 0), ms(ans, 0), ms(iscut, 0);
}
int solve() {
clean();
scanf("%d%d", &n, &m);
for (int x, y, i = 1; i <= m; ++i) {
scanf("%d%d", &x, &y);
ins(x, y), ins(y, x);
}
tarjan(1, 0);
for (int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
