[文章目录]
Description
小强建立了一个模型。这世界上有N个网络设备,他们之间有M个双向的链接。这个世界是连通的。在一段时间里,有Q个数据包要从一个网络设备发送到另一个网络设备。
一个网络设备承受的压力有多大呢?很显然,这取决于Q个数据包各自走的路径。不过,某些数据包无论走什么路径都不可避免的要通过某些网络设备。你要计算:对每个网络设备,必须通过(包括起点、终点)他的数据包有多少个?N≤100000 M,Q≤200000
求点双（缩块）模板题。（感谢CQzhangyu填坑）
建一个新图，对于同一个块内的点建一个新点与块内所有点相连，形成圆方树。原图中两点在圆方树中简单路径经过的点即为必须经过的点，求lca差分即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 101000
using namespace std;
int n,m,q,tot;
int head[N],nxt[N<<2],to[N<<2],cnt=1;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int dfn[N],low[N],z[N],top,tim;
int head1[N<<1],nxt1[N<<2],to1[N<<2],cnt1;
inline void add1(int x,int y)
{
to1[++cnt1]=y; nxt1[cnt1]=head1[x]; head1[x]=cnt1;
}
void tarjan(int x,int pa)
{
z[++top]=x; dfn[x]=low[x]=++tim; int y;
for(int i=head[x];i;i=nxt[i]) if((i^1)!=pa)
{
if(!dfn[y=to[i]])
{
tarjan(y,i); low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x])
{
int t; tot++;
do
{
t=z[top--]; add1(tot,t); add1(t,tot);
}while(t!=y);
add1(tot,x); add1(x,tot);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int deep[N<<1],fa[N<<1][18],siz[N<<1],Log[N<<1];
void dfs(int x,int pre)
{
fa[x][0]=pre;
for(int i=1;i<=Log[deep[x]];++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head1[x];i;i=nxt1[i]) if(to1[i]!=pre)
{
deep[to1[i]]=deep[x]+1;
dfs(to1[i],x);
}
}
void dfs1(int x,int pre)
{
for(int i=head1[x];i;i=nxt1[i]) if(to1[i]!=pre)
{
dfs1(to1[i],x);
siz[x]+=siz[to1[i]];
}
}
int getlca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
int tmp=deep[x]-deep[y];
for(int i=0;i<=Log[tmp];++i) if(tmp&(1<<i)) x=fa[x][i];
if(x==y) return x;
for(int i=Log[deep[x]];~i;--i)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int main()
{
scanf("%d%d%d",&n,&m,&q); int x,y;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
tot=n; tarjan(1,0);
for(int i=2;i<=tot;++i) Log[i]=Log[i>>1]+1;
dfs(1,0);
while(q--)
{
scanf("%d%d",&x,&y);
int anc=getlca(x,y);
siz[x]++; siz[y]++; siz[anc]--; siz[fa[anc][0]]--;
}
dfs1(1,0);
for(int i=1;i<=n;++i) printf("%d\n",siz[i]);
return 0;
}