题意
如今,路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的核心路由器典型的要处理100Gbit/s的网络流量。
他们每天都生活在巨大的压力之下。小强建立了一个模型。这世界上有N个网络设备,他们之间有M个双向的链接。这个世界是连通的。
在一段时间里,有Q个数据包要从一个网络设备发送到另一个网络设备。
一个网络设备承受的压力有多大呢?很显然,这取决于Q个数据包各自走的路径。
不过,某些数据包无论走什么路径都不可避免的要通过某些网络设备。
你要计算:对每个网络设备,必须通过(包括起点、终点)他的数据包有多少个?
对于40%的数据,N,M,Q≤2000
对于60%的数据,N,M,Q≤40000
对于100%的数据,N≤100000,M,Q≤200000
分析
这道题很有意思，如果它要是问可能通过的点有多少个，那问题就麻烦多了，所以它问必须经过的点，对于一个点来说，如果它不是割点，那么它一定不是必经的，除非它是端点，所以我们想到了什么？对点双联通分量，但是如果全缩了还是有问题，必须经过的点怎么办？如果变换一下这个图，让它两个点之间有唯一的路径，是不是就很好办了，对于唯一路径，我们很容易想到树，而又不能全缩了成为树，那就势必要用到别的树。
所以引入一个新的树——圆方树
这个树其实很好理解，就是原图的每个点都是圆点，方点是什么呢？一个方点对应一个点双联通分量，每个点双上的点连到这个这个方点上，这样就形成了一棵树，然后怎么办呢？如果对于每次修改都dfs一遍，显然效率是不高的，而每次发送一回数据包，就是将这一个经过的路径区间val+1，涉及区间加减，不就是差分数组嘛，所以直接u++，v++，lca--，falca--（点差分是falca--因为lca的值也要更新，边差分是lca-=2因为lca上边连着父亲节点的边是不改变的），最后直接dfs跑一遍统计答案就ok。
这里特别强调一个坑，点双连树的时候不要直接pop到割点，而是要pop到E.to，看起来是差不多的，但是在割点到E.to之间，还可能会有点，这里说的有点不是图上边，而是栈里边有没pop的值，点没有pop的原因是没有判断到割点，而那些点是显然不是这个点双里边的，连进来就是，WA，所以这里要特别注意一下。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=4e5+;
struct Edge{
int to,next;
}e[N],E[N];
int Head[N],len;
void Ins(int a,int b){
e[++len].to=b;e[len].next=Head[a];Head[a]=len;
}
int H[N],l;
void I(int a,int b){
E[++l].to=b;E[l].next=H[a];H[a]=l;
}
int low[N],dfn[N],stk[N],num,top,fang;
void tarjan(int u){
dfn[u]=low[u]=++num;
stk[++top]=u;
for(int x=Head[u];x;x=e[x].next){
int v=e[x].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
fang++;int temp;
do{
temp=stk[top--];
I(temp,fang);I(fang,temp);
}while(temp!=v);//是这里不能pop到u
I(fang,u);I(u,fang);
}
}else low[u]=min(low[u],dfn[v]);
}
}
int p[N][],dep[N];
//跑lca
void dfs(int x){
for(int i=;p[x][i];i++)
p[x][i+]=p[p[x][i]][i];
for(int i=H[x];i;i=E[i].next){
int v=E[i].to;
if(v!=p[x][]){
p[v][]=x;
dep[v]=dep[x]+;
dfs(v);
}
}
}
int Lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int d=dep[u]-dep[v];
for(int i=;d;i++,d>>=)
if(d&)u=p[u][i];
if(u==v)return u;
for(int i=;i>=;i--)//这里又写错了刚开始，i>=0不是i,i->i>0少了个0
if(p[u][i]!=p[v][i])
u=p[u][i],v=p[v][i];
return p[u][];
}
//lca结束
int val[N];
int calc(int u){
for(int i=H[u];i;i=E[i].next){
int v=E[i].to;
if(v!=p[u][])
val[u]+=calc(v);
}
return val[u];
}
int main(){
// freopen("a.txt","r",stdin);
int m,n,q;
scanf("%d%d%d",&n,&m,&q);
fang=n;
for(int i=;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
Ins(a,b);Ins(b,a);
}
tarjan();//图是联通的tarjan一遍就好
dfs();
while(q--){
int a,b;
scanf("%d%d",&a,&b);
int lca=Lca(a,b);
val[a]++;val[b]++;
val[lca]--;val[p[lca][]]--;//树上差分
}
calc();
for(int i=;i<=n;i++)
printf("%d\n",val[i]);
}