BZOJ 3331 （Tarjan缩点+树上差分）

题面

传送门

分析

用Tarjan求出割点，对点-双连通分量(v-DCC)进行缩点，图会变成一棵树
注意v-DCC的缩点和e-DCC不同，因为一个割点可能属于多个v-DCC
设图中共有p个割点和t个v-DCC,我们建立一张包含p+t个点的新图，并将每个割点和包含它的所有v-DCC连边
缩点后原图中一般点的编号为v-DCC的编号，第i个割点的编号为(v-DCC个数+i)
对于原图上的一条路径(u,v),找到u，v对应的新编号，用树上差分算法更新路径上的所有点，使次数+1
为了处理若u，v不是割点，无法更新u，v的访问次数（因为在新图上v-DCC上的所有点被缩成了一个大点，而我们却要对点u，v单独进行更新
因此，我们在原图上建立一个数组graph_count，记录第i号节点（不是割点）的访问次数
输出答案时：
-若i是割点，直接输出树上对应的割点的访问次数
-否则输出graph_count[i]

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#define maxn 200005
#define maxm 200005
#define maxlog 32
using namespace std;
int n,m,q;
inline int qread(){
    int x=0,sign=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') sign=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*sign;
}

struct graph {
    struct edge {
        int from;
        int to;
        int next;
    } E[maxm<<1];
    int head[maxn];
    int ecnt;
    void add_edge(int u,int v) {
        ecnt++;
        E[ecnt].from=u;
        E[ecnt].to=v;
        E[ecnt].next=head[u];
        head[u]=ecnt;
    }
    graph(){
        memset(head,0,sizeof(head));
        memset(E,0,sizeof(E));
        ecnt=1;
    }
};
graph G,T;

int tim,cnt,newn;
int dfn[maxn];
int low[maxn];
int cut[maxn];
int new_id[maxn]; 
int belong[maxn];
stack<int>s;
vector<int>v_dcc[maxn];
void tarjan(int x){
    int flag=0;
    dfn[x]=low[x]=++tim;
    s.push(x);
    for(int i=G.head[x];i;i=G.E[i].next){
        int y=G.E[i].to;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[y]){
                flag++;
                if(x!=1||flag>1) cut[x]=1;
                cnt++;
                int z;
                do{
                    z=s.top();
                    s.pop();
                    v_dcc[cnt].push_back(z);
                }while(z!=y);
                v_dcc[cnt].push_back(x);
            } 
        }else low[x]=min(low[x],dfn[y]);
    }
}

void graph_to_tree(){
    tim=cnt=0;
    tarjan(1);
    newn=cnt;
    for(int i=1;i<=n;i++){
        if(cut[i]){
            belong[i]=++newn;
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<v_dcc[i].size();j++){
            int x=v_dcc[i][j];
            if(cut[x]){
                T.add_edge(i,belong[x]);
                T.add_edge(belong[x],i);
            }
            else belong[x]=i;
        }
    }
}

int graph_count[maxn];
int tree_count[maxn];
int deep[maxn];
int anc[maxn][maxlog];
void lca_init(int x,int fa){
    deep[x]=deep[fa]+1;
    anc[x][0]=fa;
    for(int i=1;i<=20;i++){
        anc[x][i]=anc[anc[x][i-1]][i-1];
    }
    for(int i=T.head[x];i;i=T.E[i].next){
        int y=T.E[i].to;
        if(y!=fa){
            lca_init(y,x);
        }
    }
}

int lca(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--){
        if(deep[anc[x][i]]>=deep[y]){
            x=anc[x][i];
        }
    }
    if(x==y) return x;
    for(int i=20;i>=0;i--){
        if(anc[x][i]!=anc[y][i]){
            x=anc[x][i];
            y=anc[y][i];
        }
    }
    return anc[x][0];
}

void add_route(int u,int v){
    int l=lca(u,v);
    tree_count[l]--;
    tree_count[anc[l][0]]--;
    tree_count[u]++;
    tree_count[v]++; 
}

void sum_up(int x,int fa){
    for(int i=T.head[x];i;i=T.E[i].next){
        int y=T.E[i].to;
        if(y!=fa){
            sum_up(y,x);
            tree_count[x]+=tree_count[y];
        }
    }
}
int main() {
    int u,v,nu,nv;
    n=qread();
    m=qread();
    q=qread();
    for(int i=1;i<=m;i++){
        u=qread();
        v=qread();
        G.add_edge(u,v);
        G.add_edge(v,u);
    }
    graph_to_tree();
    lca_init(1,0);
    for(int i=1;i<=q;i++){
        u=qread();
        v=qread();
        nu=belong[u];
        nv=belong[v];
        add_route(nu,nv);
        if(!cut[u]) graph_count[u]++;
        if(!cut[v]) graph_count[v]++;
    }
    sum_up(1,0);
    for(int i=1;i<=n;i++){
        if(cut[i]){
            graph_count[i]=tree_count[belong[i]];
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d\n",graph_count[i]);
    }
}

BZOJ 3331 （Tarjan缩点+树上差分）

原文：https://www.cnblogs.com/birchtree/p/9916289.html