圆方树新技能get。具体笔记见图连通性问题学习笔记。
这题求无向图的必经点，这个是一个固定套路：首先，一张连通的无向图中，每对点双和点双之间是以一个且仅一个割点连接起来的（如果超过一个就不能是割点了），那么，在一个点双内部，从出发点开始，要走到另外一个点双中，这个中间的割点就是一条必经之路（没有其他路可以绕，否则这就有一个环了），所以，路上所有割点都是必经点，而点双内部走的话，由点双的定义，是至少有两条点不相交的路径的（当然两个点的点双的话直接没有中间点），所以中间非割点是可经而不是必经的。
所以，构建圆方树，起始点和终止点构成的路径上所有圆点就是答案。然后，依题意做树上差分即可。
为什么我线性求lca还跑不过log的啊。。
圆方树构建的code大致是模仿zsy写的。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define mst(x) memset(x,0,sizeof x)
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<" "<< #y <<" = "<< y <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=1e5+;
struct thxorz{
int to[N<<],nxt[N<<],head[N<<],tot;
inline void add(int x,int y){
to[++tot]=y,nxt[tot]=head[x],head[x]=tot;
to[++tot]=x,nxt[tot]=head[y],head[y]=tot;
}
}G1,G2,Q;
int n,m,q;
int tag[N<<],fa[N<<],anc[N<<],vis[N<<];
int Find(int x){return anc[x]==x?x:anc[x]=Find(anc[x]);}
#define y G2.to[j]
#define qy Q.to[j]
void tarjan_lca(int x,int fat){
anc[x]=x;fa[x]=fat;
for(register int j=G2.head[x];j;j=G2.nxt[j])if(fat^y)tarjan_lca(y,x),anc[y]=x;
vis[x]=;int tmp;
for(register int j=Q.head[x];j;j=Q.nxt[j])if(vis[qy])tmp=Find(qy),--tag[tmp],--tag[fa[tmp]];
}
void dfs(int x){for(register int j=G2.head[x];j;j=G2.nxt[j])if(fa[x]^y)dfs(y),tag[x]+=tag[y];}
#undef y
#undef qy
#define y G1.to[j]
int dfn[N],low[N],stk[N],Top,tim,cnt;
void tarjan(int x){//promise:connected,without vertexes isolated.
dfn[x]=low[x]=++tim;stk[++Top]=x;
for(register int j=G1.head[x];j;j=G1.nxt[j]){
if(!dfn[y]){//We needn't get the cut-vertexes,and cut-vertexes have nothing to do with v-DCCs.
tarjan(y),MIN(low[x],low[y]);
if(dfn[x]==low[y]){
int tmp;++cnt;
do tmp=stk[Top--],G2.add(tmp,cnt);while(tmp^y);
G2.add(x,cnt);
}
}
else MIN(low[x],dfn[y]);
}
}
#undef y
int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
cnt=read(n),read(m),read(q);
for(register int i=,x,y;i<=m;++i)read(x),read(y),G1.add(x,y);
for(register int i=;i<=n;++i)if(!dfn[i])Top=,tarjan(i);
for(register int i=,x,y;i<=q;++i)read(x),read(y),Q.add(x,y),++tag[x],++tag[y];
tarjan_lca(,);dfs();
for(register int i=;i<=n;++i)printf("%d\n",tag[i]);
return ;
}
总结：图中简单路径问题，经过点的统计问题，考虑从点双和圆方树入手。
顺带一提，点双缩点一般配合圆方树食用，而边双直接缩成一棵树，比如这题如果问必经边的话，一定是割边是必经边（证明同理），只要缩边双后在树上直接差分即可。