传送门

Tarjan的三大应用之一：求解点双联通分量。

求解点双联通分量。然后缩点，差分优化即可。

//BZOJ 3331//by Cydiater//2016.10.29#include <iostream>#include <cmath>#include <cstdlib>#include <cstdio>#include <queue>#include <map>#include <cstring>#include <string>#include <algorithm>#include <set>#include <bitset>#include <iomanip>#include <ctime>#include <vector>using namespace std;#define ll long long#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)#define cmax(a,b) a=max(a,b)#define cmin(a,b) a=min(a,b)#define Auto(i,a) for(int i=LINK[a];i;i=e[i].next)#define vci vector<int>#define pb push_backconst int MAXN=4e5+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,M,Q,lable[MAXN],dfn[MAXN],low[MAXN],stack[MAXN],top=0,dfs_clock=0,fa[MAXN][25],dep[MAXN],group_num=0;vci group[MAXN];struct edge{int x,y,next;};struct Graph{	int LINK[MAXN],len;	Graph(){memset(LINK,0,sizeof(LINK));len=0;}	edge e[MAXN];	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].x=x;}	inline void Insert(int x,int y){insert(x,y);insert(y,x);}	void tarjan(int node){		dfn[node]=low[node]=++dfs_clock;		stack[++top]=node;int son=0;		Auto(i,node)if(!dfn[e[i].y]){			tarjan(e[i].y);			cmin(low[node],low[e[i].y]);			if(low[e[i].y]>=dfn[node]){				int tmp;group_num++;				do{					tmp=stack[top--];					group[group_num].pb(tmp);				}while(tmp!=e[i].y);				group[group_num].pb(node);			}		}else cmin(low[node],dfn[e[i].y]);	}	void dfs(int node,int deep,int father){		fa[node][0]=father;dep[node]=deep;		Auto(i,node)if(e[i].y!=father)dfs(e[i].y,deep+1,node);	}	void get_ancestor(){		up(i,1,20)up(node,1,N+group_num)if(fa[node][i-1])			fa[node][i]=fa[fa[node][i-1]][i-1];	}	int LCA(int x,int y){		if(x==y)		return x;		if(dep[x]<dep[y])swap(x,y);		down(i,20,0)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];		if(x==y)		return x;		down(i,20,0)if(fa[x][i]!=0&&fa[x][i]!=fa[y][i]){			x=fa[x][i];y=fa[y][i];		}		return fa[x][0];	}	void re_dfs(int node){		Auto(i,node)if(e[i].y!=fa[node][0]){			re_dfs(e[i].y);			lable[node]+=lable[e[i].y];		}	}}G1,G2;namespace solution{	void init(){		N=read();M=read();Q=read();		up(i,1,M){			int x=read(),y=read();			G1.Insert(x,y);		}	}	void slove(){		G1.tarjan(1);		up(i,1,group_num)up(j,0,group[i].size()-1)G2.Insert(i+N,group[i][j]);		G2.dfs(1,0,0);G2.get_ancestor();		memset(lable,0,sizeof(lable));		while(Q--){			int x=read(),y=read(),lca=G2.LCA(x,y);			lable[x]++;lable[y]++;lable[lca]--;lable[fa[lca][0]]--;		}		G2.re_dfs(1);	}	void output(){		up(i,1,N)printf("%d\n",lable[i]);	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	init();	slove();	output();	return 0;}

BZOJ3331: [BeiJing2013]压力