Description
如今，路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的核心路由器典型的要处理100Gbit/s的网络流量。他们每天都生活在巨大的压力之下。 小强建立了一个模型。这世界上有N个网络设备，他们之间有M个双向的链接。这个世界是连通的。在一段时间里，有Q个数据包要从一个网络设备发送到另一个网络设备。 一个网络设备承受的压力有多大呢？很显然，这取决于Q个数据包各自走的路径。不过，某些数据包无论走什么路径都不可避免的要通过某些网络设备。 你要计算：对每个网络设备，必须通过（包括起点、终点）他的数据包有多少个？
Input
第一行包含3个由空格隔开的正整数N，M，Q。 接下来M行，每行两个整数u，v，表示第u个网络设备（从1开始编号）和第v个网络设备之间有一个链接。u不会等于v。两个网络设备之间可能有多个链接。 接下来Q行，每行两个整数p，q，表示第p个网络设备向第q个网络设备发送了一个数据包。p不会等于q。
Output
输出N行，每行1个整数，表示必须通过某个网络设备的数据包的数量。
Sample Input
4 4 2 1 2 1 3 2 3 1 4 4 2 4 3
Sample Output
2 1 1 2 【样例解释】 设备1、2、3之间两两有链接，4只和1有链接。4想向2和3各发送一个数据包。显然，这两个数据包必须要经过它的起点、终点和1。
Data Constraint
对于40%的数据，N，M，Q≤2000 对于60%的数据，N，M，Q≤40000 对于100%的数据，N≤100000，M，Q≤200000
题解
- 题目大意：给出一个 N 个点，M 条边的连通图，和 M 个点对。询问删掉每个点会使 M 个点对中的几个不连通
- 其实就类似于求路径上有多少个割点
- 首先，可以tarjan求点双分量，然后建新点，也就是缩点
- 最后得到一颗树
- 然后就在树上求两点的lca
- 最后就是差分了
- 那么怎么做？
- 将x,y点++，lca--，lca的父亲--
- 那么怎么处理在路径上的割点呢？
- 在倍增时，记录对于新建点的父亲
- 那新建点也就是缩点后的点与父亲只有一条路径
- 那么就可以将父亲的差分+当前点的差分，一步一步将树向上加
代码
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 struct edge { int to,from; }e[200010*2],c[200010*2];10 int n,m,q,dis,tot,cnt,num,cnt1,cnt2,head[200010],last[200010],dfn[100010],low[100010],k[100010],sh[200010],f[200010][21],dep[200010],d[200010];11 void insert(int x,int y) { e[++cnt].to=y; e[cnt].from=head[x]; head[x]=cnt; }12 void insert1(int x,int y) { c[++cnt2].to=y; c[cnt2].from=last[x]; last[x]=cnt2; }13 void tarjan(int x)14 {15 dfn[x]=low[x]=++cnt1; k[++num]=x;16 for (int i=head[x];i;i=e[i].from)17 {18 int v=e[i].to;19 if (dfn[v]==-1)20 {21 tarjan(v);22 low[x]=min(low[x],low[v]);23 if (low[v]>=dfn[x])24 {25 tot++;26 int j;27 do28 {29 j=k[num--]; 30 insert1(tot,j); insert1(j,tot);31 }32 while (j!=v);33 insert1(x,tot);insert1(tot,x);34 }35 }36 else low[x]=min(low[x],dfn[v]);37 }38 }39 void dfs(int x,int fa)40 {41 sh[sh[0]++]=x; f[x][0]=fa;42 for (int i=1;i<=20;i++) f[x][i]=f[f[x][i-1]][i-1];43 for (int i=last[x];i;i=c[i].from)44 {45 int v=c[i].to;46 if (v==fa) continue;47 dep[v]=dep[x]+1;48 dfs(v,x);49 }50 }51 int lca(int x,int y)52 {53 if (dep[x]>dep[y]) swap(x,y);54 for (int i=20;i>=0;i--)55 if (dep[f[y][i]]>=dep[x])56 y=f[y][i];57 if (x==y) return x;58 for (int i=20;i>=0;i--)59 if (f[x][i]!=f[y][i])60 x=f[x][i],y=f[y][i];61 return f[x][0];62 }63 int main()64 {65 scanf("%d%d%d",&n,&m,&q);66 tot=n;67 for (int i=1;i<=m;i++)68 {69 int u,v; 70 scanf("%d%d",&u,&v);71 insert(u,v); insert(v,u);72 }73 memset(dfn,-1,sizeof(dfn));74 tarjan(1);75 dep[1]=1; dfs(1,0);76 for (int i=1;i<=q;i++)77 {78 int x,y;79 scanf("%d%d",&x,&y);80 dis=lca(x,y);81 d[x]++; d[y]++; d[dis]--; d[f[dis][0]]--;82 }83 for (int i=tot;i>=1;i--) 84 {85 int now=sh[i];86 d[f[now][0]]+=d[now];87 }88 for (int i=1;i<=n;i++) printf("%d\n",d[i]);89 return 0;90 }