bzoj3331 [BeiJing2013]压力

最新推荐文章于 2020-02-18 11:27:58 发布

wanherun

最新推荐文章于 2020-02-18 11:27:58 发布

阅读量554

点赞数

分类专栏：刷题总结 tarjan 文章标签：图论 tarjan

本文链接：https://blog.csdn.net/wanherun/article/details/79178116

版权

刷题总结同时被 2 个专栏收录

285 篇文章

订阅专栏

tarjan

4 篇文章

订阅专栏

本文介绍了一种解决特定图论问题的方法，通过寻找图中的点双联通分量并进行树上差分操作来求解。具体步骤包括使用Tarjan算法识别割点与双连通块，构建新的树形结构，并利用树上差分技巧快速求解子树上的累加和。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

显然，如果两个点之间要有一个必须到达的点，这个点必须是割点。只要我们求出点双联通分量，然后对图重构，在新得到的树上做就好了。

我们在树上就可以差分了，最后求一个子树和就好了。

#include<bits/stdc++.h>
#define N 500000 
using namespace std;
int first[N+5],nxt[N+5],to[N+5],siz;
int First[N+5],Nxt[N+5],To[N+5],Siz;
int dfn[N+5],low[N+5],ind;
int stk[N+5],top,dep[N+5];
int n,m,q,x,y,sum,z,ans[N+5];
int f[N+5][30],s[N+5];
inline void Link(int x,int y)
{
    Nxt[Siz]=First[x];
    First[x]=Siz;
    To[Siz++]=y;
}
inline void link(int x,int y)
{
    nxt[siz]=first[x];
    first[x]=siz;
    to[siz++]=y;
}
inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x=0,b=1;
    char c=nc();
    for(;!(c<='9'&&c>='0');c=nc())if(c=='-')b=-1;
    for(;c<='9'&&c>='0';c=nc())x=x*10+c-'0';
    return x*b;
}
inline void tarjan(int x)
{
    dfn[x]=low[x]=++ind;
    stk[++top]=x;
    for(int i=first[x];i!=-1;i=nxt[i])
    {
        int u=to[i];
        if(!dfn[u])
        {
            tarjan(u),low[x]=min(low[x],low[u]);
            if(low[u]>=dfn[x])
            {
                int tmp;sum++;
                do
                {
                    tmp=stk[top--],Link(sum,tmp),Link(tmp,sum);
                }while(tmp!=u);
                Link(sum,x),Link(x,sum);
            }
        }else low[x]=min(low[x],dfn[u]);
    }
}
inline void dfs(int x,int fa)
{
    for(int i=1;i<=25;i++)if(f[x][i-1])f[x][i]=f[f[x][i-1]][i-1];
    else break;dep[x]=dep[fa]+1;
    for(int i=First[x];i!=-1;i=Nxt[i])
    {
        int u=To[i];
        if(u==fa)continue;
        f[u][0]=x;dfs(u,x);
    }
}
inline int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    int fet=dep[x]-dep[y];
    for(int i=25;i>=0;i--)if(fet>=(1<<i))fet-=(1<<i),x=f[x][i];
    if(x==y)return x;
    for(int i=25;i>=0;i--)
        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
inline void cal(int x,int fa)
{
    ans[x]=s[x];
    for(int i=First[x];i!=-1;i=Nxt[i])
    {
        int u=To[i];
        if(u==fa)continue;
        cal(u,x);
        ans[x]+=ans[u];
    }
}
int main()
{
    freopen("in.txt","r",stdin);
    n=read(),m=read(),q=read(),sum=n;
    memset(first,-1,sizeof(first));
    memset(First,-1,sizeof(First));
    for(int i=1;i<=m;i++)x=read(),y=read(),link(x,y),link(y,x);
    tarjan(1);dfs(1,0);
    for(int i=1;i<=q;i++)
    {
        x=read(),y=read(),z=lca(x,y);
        s[x]++,s[y]++,s[z]--,s[f[z][0]]--;
    }
    cal(1,0);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}