压力 | Hexo

归档于 2019-07-15 21:08

首先如果路径上有割点一定是必经点，然后如果是环上的点（除了割点）一定有多条路径可以到，所以环上（除了割点起点终点）都不必经。

所以点双缩点，重新建图（普通建图or圆方）

那么对于每组询问lca加普通树差标记一下，

对于每组询问拿数组zz记录起点终点，

最后dfs扫一遍

，结束时如果不为割点，直接输出zz

否则输出dfs扫出的ans

必经点模版题

#include<bits/stdc++.h>
#define ll long long
#define pt printf("******\n")
#define A 1000000
using namespace std;
ll tot=0,head[A],sta[A],low[A],dfn[A],nxt[A],ver[A],deep[A],belong[A],cut[A];
ll tc=0,head_c[A],nxt_c[A],ver_c[A],sz[A],f[A][30],ans[A],zz[A];
ll n,m,q,t,num=0,cnt=0,root,top=0;
vector<ll> scc[A];
bool flag[A],vis[A];
void add(ll x,ll y){
    nxt[++tot]=head[x],head[x]=tot,ver[tot]=y;
}
void add_c(ll x,ll y){
    nxt_c[++tc]=head_c[x],head_c[x]=tc,ver_c[tc]=y;
}
void tarjan(ll x){
    low[x]=dfn[x]=++num;
    sta[++top]=x;ll vis=0;
    if(x==root&&!head[x])
    {
        cnt++;
        belong[x]=cnt;
        scc[cnt].push_back(x);
    }
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[y]){
                vis++;
                if(x!=root||vis>1) cut[x]=1;
                cnt++;
                ll z;
                do{
                    z=sta[top--];
                    belong[z]=cnt;
                    scc[cnt].push_back(z);
                }while(z!=y);
                belong[x]=cnt;
                scc[cnt].push_back(x);
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
inline ll lca(ll x,ll y){
    if(deep[x]>deep[y]) swap(x,y);
    ll w;
    for(w=0;(1<<w)<=deep[y];w++);
    w--;
    for(ll i=w;i>=0;i--)
    {
//        printf("deep[%lld]=%lld deep[%lld]=%lld f[%lld]=%lld\n",x,deep[x],y,deep[y],i,f[y][i]);
        
        if(deep[x]<=deep[f[y][i]]) y=f[y][i];
        if(deep[x]==deep[y]) break;
    }
    if(x==y) return x;
    for(ll i=w;i>=0;i--){
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    }
    return f[y][0];
}
void dfs2(ll x,ll de){
    deep[x]=de;flag[x]=1;
    for(ll i=head_c[x];i;i=nxt_c[i]){
        ll y=ver_c[i];
        if(flag[y])
            continue;
        f[y][0]=x;
        dfs2(y,de+1);
    }
}
ll dfs3(ll x){
    vis[x]=1;
    for(ll i=head_c[x];i;i=nxt_c[i]){
        ll y=ver_c[i];
        if(vis[y]) continue;
        ll to=dfs3(y);
        ans[x]+=to;
    }
    return ans[x];
}
int main(){
//    freopen("mkd.txt","r",stdin);
//    freopen("wa.txt","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&q);
    t=log(n)/log(2)+5;
    for(ll i=1;i<=m;i++){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y);add(y,x);
    }
    for(ll i=1;i<=n;i++){
        if(!dfn[i]) root=i,tarjan(i);
    }
    num=cnt;
    for(ll i=1;i<=n;i++)
    if(cut[i]) belong[i]=++num/*,printf("gd=%lld\n",i)*/;
    for(ll i=1;i<=cnt;i++){
        ll size=scc[i].size();
        for(ll j=0;j<size;j++){
            if(cut[scc[i][j]]){
                add_c(i,belong[scc[i][j]]);
                add_c(belong[scc[i][j]],i);
            }
        }
    }
    dfs2(1,1),f[1][0]=1;
    for(ll j=1;j<=t;j++)
        for(ll i=1;i<=num;i++)
            f[i][j]=f[f[i][j-1]][j-1];
    /*for(ll i=1;i<=n;i++){
        printf("belong=%lld\n",belong[i]);    
    }
    for(ll i=1;i<=num;i++)
    {
        printf("deep[i]=%lld f[i][0]=%lld belong=%lld\n",deep[belong[i]],f[belong[i]][0],belong[i]);
    }*/
    for(ll i=1;i<=q;i++){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        ll lc=lca(belong[x],belong[y]);
//        cout<<lc<<endl;
        zz[x]++,zz[y]++;
//        printf("x=%lld y=%lld lc=%lld lf=%lld\n",belong[x],belong[y],lc,f[lc][0]);
        ans[belong[x]]++;
        ans[belong[y]]++;
        ans[lc]--;
        if(f[lc][0]!=lc)ans[f[lc][0]]--;
    }
    dfs3(1);
    for(ll i=1;i<=n;i++){
        if(cut[i]) cout<<ans[belong[i]]<<endl;
        else cout<<zz[i]<<endl;
    }
    return 0;
}

View Code