[BZOJ3331][BeiJing2013]压力-526互联

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>

using namespace std;

vector <int> temp[5211314], bcc[5211314]; 
int n, m, q;
int next_[5211314], head[5211314], to[5211314], cnt;
int op[5211314], stack[5211314], top_num;
//op表示i是否在栈内，top_num表示栈的长度
int num, dfn[5211314], low[5211314], poi_num;
int deep[5211314], son[5211314], size[5211314], fa[5211314], top[5211314];
int sum[5211314];

inline void add_poi( int v1 , int v2 ) {
	++ cnt;
	next_[cnt] = head[v1];
	head[v1] = cnt;
	to[cnt] = v2;
	return;
}

void tarjan( int now ) {
	stack[++ top_num] = now;
	op[now] = true;
	dfn[now] = low[now] = ++ num;
	for (int i = head[now]; i != 0; i = next_[i]) {
		if ( dfn[to[i]] == 0 ) {
			tarjan( to[i] );
			low[now] = min( low[now] , low[to[i]] );
			if ( low[to[i]] >= dfn[now] ) {
				poi_num ++;
				int tem;
				do {
					tem = stack[top_num];
					top_num --;
					bcc[poi_num].push_back( tem );
					op[tem] = false;
				} while( tem != to[i] );
				bcc[poi_num].push_back( now );
			}//求点双 圆方树
		}
		else if ( op[to[i]] = true ) {
			low[now] = min( low[now] , dfn[to[i]] );
		}
	}
	return;
}

void build_new_edg() {
	for (int i = 1, x; i <= poi_num; ++ i) {
		for (int j = 0; j < bcc[i].size(); ++ j) {
			x = bcc[i][j];
			temp[x].push_back( i + n );
			//第i个点双的编号为i+n
			//这里表示点x与编号为i的点双连接
			temp[i + n].push_back( x );
		}
	}
	return;
}

void dfs_son( int now , int father ) {
	fa[now] = father;
	deep[now] = deep[father] + 1;
	size[now] = 1;
	for (int i = 0, to_poi; i < temp[now].size(); ++ i) {
		to_poi = temp[now][i];
		if ( to_poi != father ) {
			dfs_son( to_poi , now );
			size[now] += size[to_poi];
			if ( size[son[now]] < size[to_poi] ) {
				son[now] = to_poi;
			}
		}
	}
	return;
}

void dfs_line( int now , int top_ ) {
	top[now] = top_;
	if ( son[now] ) {
		dfs_line( son[now] , top_ );
	}
	for (int i = 0, to_poi; i < temp[now].size(); ++ i) {
		to_poi = temp[now][i];
		if ( to_poi != fa[now] && to_poi != son[now] ) {
			dfs_line( to_poi , to_poi );
		}
	}
	return;
}//正常树链剖分

int lca( int x , int y ) {
	while ( top[x] != top[y] ) {
		if ( deep[top[x]] < deep[top[y]] ) swap( x , y );
		x = fa[top[x]];
	}
	if ( deep[x] < deep[y] ) swap( x , y );
	//此时y的深度小，且x与y在同一条链上，则此时y为初始未更改之前的x和y的lca
	return y;
}

void update( int now ) {
	for (int i = 0, to_poi; i < temp[now].size(); ++ i) {
		to_poi = temp[now][i];
		if ( to_poi != fa[now] ) {
			update( to_poi );
			sum[now] += sum[to_poi];
		}
	}
	return;
}

int main() {
	freopen("pressure.in","r",stdin);
	freopen("pressure.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for (int i = 1, u, v; i <= m; ++ i) {
		scanf("%d%d",&u,&v);
		add_poi( u , v );
		add_poi( v , u );
	}
	tarjan( 1 );
	build_new_edg();
	dfs_son( 1 , 0 );
	dfs_line( 1 , 1 );
	for (int i = 1, u, v; i <= q; ++ i) {
		scanf("%d%d",&u,&v);
		int Lca = lca( u , v );
		sum[u] ++;
		sum[v] ++;
		sum[Lca] --;
		//因为下面要求所有儿子走过的次数的和会在两点的lca处加2次
		//所以要减去1次
		sum[fa[Lca]] --;
		//这列减一因为此时Lca的父亲并没有走到,所以更新时加上的1要减去
	}
	update( 1 );
	for (int i = 1; i <= n; ++ i) {
		printf("%d\n",sum[i]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}