Luogu 2783 有机化学之神偶尔会做作弊

去年NOIP之前做的,人生中第一道黑题,真是可喜可贺可喜可贺(虽然参考了题解) Tarjan缩点重新构图,然后统计题目给定两点的树上距离即可。 上代码

    
    // luogu-judger-enable-o2
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<queue>
    #include<stack>
    using namespace std;
    
    //define
    const int maxn=1e4+5;
    const int maxm=5e4+5;
    
    struct Edge{ int v,next; }e[maxm*2],e2[maxm*2];
    int head[maxn],dfn[maxn],low[maxn],visx,head2[maxn],tot,fa[maxn][25],belong[maxn],m,n,tot2,dep[maxn],xx[maxm],yy[maxm];
    bool exist[maxn];
    stack<int> st;
    
    inline void addedge(int u,int v){
        e[++tot].v=v;e[tot].next=head[u];head[u]=tot;
    }
    int cnt;
    void tj(int u,int from){
        low[u]=dfn[u]= ++visx; st.push(u); exist[u]=true;
        for(register int i=head[u];i;i=e[i].next){
            int v=e[i].v;
            if(v==from) continue;
            if(dfn[v]==-1) tj(v,u),low[u]=min(low[u],low[v]);
            else if(exist[v]) low[u]=min(low[u],dfn[v]);
        }
        if(dfn[u]==low[u]){
            ++cnt;
            while(1){
                int v=st.top();st.pop();
                exist[v]=0; belong[v]=cnt;
                if(v==u) break;
            }
        }
    }
    
    inline void addedge2(int u,int v){
        e2[++tot2].v=v;e2[tot2].next=head2[u];head2[u]=tot2;
    }
    
    void dfs(int u,int from,int deepth){
        dep[u]=deepth; fa[u][0]=from;
        for(register int i=head2[u];i;i=e2[i].next){
            int v=e2[i].v;
            if(v!=from) dfs(v,u,deepth+1);
        }
    }
    
    int lca(int u,int v){
        if(dep[u]<dep[v]) swap(u,v);
        for(register int j=0;j<=22;j++)
            if((dep[u]-dep[v])&(1<<j)) u=fa[u][j];
        if(u==v) return u;
        for(register int i=22;i>=0;i--)
            if(fa[u][i]!=fa[v][i]){
                u=fa[u][i],v=fa[v][i];
            }
        return fa[u][0];
    }
    
    int ans[28000];
    int change(int n){
        int cur=0;
        if(n==0){ cout<<'0';return 0; }
        if(n<0) { putchar('-');n=0-n; }
        while(n){
            ans[++cur]=n%2;n/=2;
        }
        for(register int i=cur;i>=1;i--) cout<<ans[i];
        cout<<endl;
    }
    
    int main(){
        cin>>n>>m;
        memset(dfn,-1,sizeof dfn );
        memset(low,-1,sizeof low );
        for(register int i=1;i<=m;i++){
            int u,v;cin>>u>>v;
            xx[i]=u,yy[i]=v;
            addedge(u,v),addedge(v,u);
        }
        for(register int i=1;i<=n;i++)
            if(dfn[i]==-1)
                tj(i,-1);
        for(register int i=1;i<=m;i++){
            if(belong[xx[i]]!=belong[yy[i]]){
                addedge2(belong[xx[i]],belong[yy[i]]);
                addedge2(belong[yy[i]],belong[xx[i]]);
            }
        }
        dfs(belong[1],belong[1],0);
        for(register int j=1;j<=22;j++)
            for(register int i=1;i<=cnt;i++)
                fa[i][j]=fa[fa[i][j-1]][j-1];
        int T;cin>>T;
        while(T--){
            int u,v;cin>>u>>v;
            int ans=lca(belong[u],belong[v]);
            change(dep[belong[u]]+dep[belong[v]]-dep[ans]-dep[ans]+1);//二进制格式输入距离
        }
        return 0;
    }