【BZOJ 1123】[POI2008] BLO

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1123

就是求一求BCC
在求BCC的时候顺便统计一下答案

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = 1000000+9;

int n,m,head[N],nxt[M],to[M],sz[N];
int lowlink[N],num[N],bcc_cnt,num_cnt; 
LL vout[N];
vector<int> bcc_num[N];
stack<int> stk;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

void Tarjan(int w, int f) {
	lowlink[w] = num[w] = ++num_cnt;
	stk.push(w); sz[w] = 1; int tmp = 0;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
		if (!num[to[i]]) {
			Tarjan(to[i], w);
			sz[w] += sz[to[i]];
			lowlink[w] = min(lowlink[w], lowlink[to[i]]);
			if (lowlink[to[i]] >= num[w]) {
				int cur; bcc_cnt++;
				do {
					cur = stk.top(); stk.pop();
					bcc_num[cur].push_back(bcc_cnt);
				} while (cur != to[i]);
				vout[w] += 2LL * tmp * sz[to[i]];
				tmp += sz[to[i]];
			}
		} else {
			lowlink[w] = min(num[to[i]], lowlink[w]);
		}
	}
	vout[w] += 2LL * tmp * (n - tmp - 1) + 2 * (n - 1);
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}	

int main(){
	n = read(); m = read();
	for (int i=1;i<=m;i++) {
		Add_Edge(read(),read());
	}
	Tarjan(1,1);
	for (int i=1;i<=n;i++) {
		printf("%lld\n",vout[i]);
	} 
	return 0;
}