题面
分析
用Tarjan求出割点，对点-双连通分量(v-DCC)进行缩点，图会变成一棵树
注意v-DCC的缩点和e-DCC不同，因为一个割点可能属于多个v-DCC
设图中共有p个割点和t个v-DCC,我们建立一张包含p+t个点的新图，并将每个割点和包含它的所有v-DCC连边
缩点后原图中一般点的编号为v-DCC的编号，第i个割点的编号为(v-DCC个数+i)
对于原图上的一条路径(u,v),找到u，v对应的新编号，用树上差分算法更新路径上的所有点，使次数+1
为了处理若u，v不是割点，无法更新u，v的访问次数（因为在新图上v-DCC上的所有点被缩成了一个大点，而我们却要对点u，v单独进行更新
因此，我们在原图上建立一个数组graph_count，记录第i号节点（不是割点）的访问次数
输出答案时：
-若i是割点，直接输出树上对应的割点的访问次数
-否则输出graph_count[i]
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#define maxn 200005
#define maxm 200005
#define maxlog 32
using namespace std;
int n,m,q;
inline int qread(){
int x=0,sign=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') sign=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*sign;
}
struct graph {
struct edge {
int from;
int to;
int next;
} E[maxm<<1];
int head[maxn];
int ecnt;
void add_edge(int u,int v) {
ecnt++;
E[ecnt].from=u;
E[ecnt].to=v;
E[ecnt].next=head[u];
head[u]=ecnt;
}
graph(){
memset(head,0,sizeof(head));
memset(E,0,sizeof(E));
ecnt=1;
}
};
graph G,T;
int tim,cnt,newn;
int dfn[maxn];
int low[maxn];
int cut[maxn];
int new_id[maxn];
int belong[maxn];
stack<int>s;
vector<int>v_dcc[maxn];
void tarjan(int x){
int flag=0;
dfn[x]=low[x]=++tim;
s.push(x);
for(int i=G.head[x];i;i=G.E[i].next){
int y=G.E[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
flag++;
if(x!=1||flag>1) cut[x]=1;
cnt++;
int z;
do{
z=s.top();
s.pop();
v_dcc[cnt].push_back(z);
}while(z!=y);
v_dcc[cnt].push_back(x);
}
}else low[x]=min(low[x],dfn[y]);
}
}
void graph_to_tree(){
tim=cnt=0;
tarjan(1);
newn=cnt;
for(int i=1;i<=n;i++){
if(cut[i]){
belong[i]=++newn;
}
}
for(int i=1;i<=cnt;i++){
for(int j=0;j<v_dcc[i].size();j++){
int x=v_dcc[i][j];
if(cut[x]){
T.add_edge(i,belong[x]);
T.add_edge(belong[x],i);
}
else belong[x]=i;
}
}
}
int graph_count[maxn];
int tree_count[maxn];
int deep[maxn];
int anc[maxn][maxlog];
void lca_init(int x,int fa){
deep[x]=deep[fa]+1;
anc[x][0]=fa;
for(int i=1;i<=20;i++){
anc[x][i]=anc[anc[x][i-1]][i-1];
}
for(int i=T.head[x];i;i=T.E[i].next){
int y=T.E[i].to;
if(y!=fa){
lca_init(y,x);
}
}
}
int lca(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
for(int i=20;i>=0;i--){
if(deep[anc[x][i]]>=deep[y]){
x=anc[x][i];
}
}
if(x==y) return x;
for(int i=20;i>=0;i--){
if(anc[x][i]!=anc[y][i]){
x=anc[x][i];
y=anc[y][i];
}
}
return anc[x][0];
}
void add_route(int u,int v){
int l=lca(u,v);
tree_count[l]--;
tree_count[anc[l][0]]--;
tree_count[u]++;
tree_count[v]++;
}
void sum_up(int x,int fa){
for(int i=T.head[x];i;i=T.E[i].next){
int y=T.E[i].to;
if(y!=fa){
sum_up(y,x);
tree_count[x]+=tree_count[y];
}
}
}
int main() {
int u,v,nu,nv;
n=qread();
m=qread();
q=qread();
for(int i=1;i<=m;i++){
u=qread();
v=qread();
G.add_edge(u,v);
G.add_edge(v,u);
}
graph_to_tree();
lca_init(1,0);
for(int i=1;i<=q;i++){
u=qread();
v=qread();
nu=belong[u];
nv=belong[v];
add_route(nu,nv);
if(!cut[u]) graph_count[u]++;
if(!cut[v]) graph_count[v]++;
}
sum_up(1,0);
for(int i=1;i<=n;i++){
if(cut[i]){
graph_count[i]=tree_count[belong[i]];
}
}
for(int i=1;i<=n;i++){
printf("%d
",graph_count[i]);
}
}