BZOJ-3331: [BeiJing2013]压力

[文章目录]

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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注