题解 P2783 【有机化学之神偶尔会做作弊】

· · 题解

终于有机会写一道黑题至少目前是这样的题解了！小蒟蒻好兴奋qwq

这道题可以说是非常水了，方法都差不多，基本上就是先用tarjan求双联通分量缩一下点，然后再重新建图进行处理，最后把答案转化为二进制。

看各位dalao都是缩点后求出lca再直接计算的（*depth[x]+depth[y]-depth[lca]2+1**）

小蒟蒻这里提供一种在树剖中直接求出答案的方法（似乎本质上并没有区别）权当是一种思路吧qwq

int qrange(int x,int y){
    int ress=0;
    while(top[x]!=top[y]){  
        if(depth[top[x]]<depth[top[y]])
          swap(x,y);
        ress+=depth[x]-depth[top[x]]+1;
        x=fa[top[x]];
    }
    if(depth[x]>depth[y])
      swap(x,y);
    int ree=depth[y]-depth[x]+1;
    return ress+ree;
}

在树剖每次跳链的时候顺便求出走过的碳的数量，这样就不用专门求lca了（雾

有dalao说必须要用vector存边，小蒟蒻瑟瑟发抖，思量再三最后还是用的邻接表，然而就过了(雾

程序中还有简单的注解，小蒟蒻在这里就不多说了qwq

那么代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
#define maxn 200010
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;i++)
using namespace std;

int n,m,k,c,t,cnt,num,num1,tot,co,x,y,z;
int ans[maxn],head1[maxn],depth[maxn],fa[maxn],son[maxn],head2[maxn];
int a[maxn],low[maxn],dfn[maxn],val[maxn],b[maxn],siz[maxn],top[maxn]; 
int shu[100010],id[maxn];

struct hz{
    int next;
    int to;
    int ff;
}h1[maxn],h2[maxn]; //邻接表存图

stack<int> st;

inline void in(int &x){ //无处不在的快读
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c==-1) return;
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    x=x*f;
}

inline void out(int a){
    if(a<0){
        a*=-1;
        putchar('-');
    } 
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

void add1(int from,int to){  //读入时的加边
    h1[++num].next=head1[from];
    h1[num].ff=from;
    h1[num].to=to;
    head1[from]=num;
}

void add2(int from,int to){ //缩点后的加边
    h2[++num1].next=head2[from];
    h2[num1].to=to;
    head2[from]=num1;
}

void tarjan(int x,int f){ //tarjan求双连通分量
    dfn[x]=low[x]=++tot;
    b[x]=1;
    st.push(x);
    for(re int i=head1[x];i!=0;i=h1[i].next){
        if(h1[i].to==f) //和tarjan求强联通分量略用差别，不能走回父节点
          continue;
        if(dfn[h1[i].to]==0){
            tarjan(h1[i].to,x);
            low[x]=min(low[x],low[h1[i].to]);
        }
        else
          if(b[h1[i].to]==1)
            low[x]=min(low[x],dfn[h1[i].to]);
    }
    if(dfn[x]==low[x]){
        ++co;
        while(x!=st.top()){
            b[st.top()]=0;
            a[st.top()]=co;
            st.pop();
        }
        b[x]=0;
        a[x]=co;
        st.pop();
    }
}

void dfs1(int f,int ff){ 
    depth[f]=depth[ff]+1;
    fa[f]=ff;
    siz[f]=1;
    for(re int i=head2[f];i!=0;i=h2[i].next){
        if(h2[i].to==ff)
          continue;
        dfs1(h2[i].to,f);
        siz[f]+=siz[h2[i].to];
        if(siz[h2[i].to]>siz[son[f]])
          son[f]=h2[i].to;
    }
}

void dfs2(int x,int topf){ 
    top[x]=topf;
    id[x]=++cnt;
    if(!son[x])
      return;
    dfs2(son[x],topf);
    for(re int i=head2[x];i!=0;i=h2[i].next){
        if(h2[i].to==fa[x]||h2[i].to==son[x])
          continue;
        dfs2(h2[i].to,h2[i].to);
    }
}

int qrange(int x,int y){ //树剖求答案
    int ress=0;
    while(top[x]!=top[y]){
        if(depth[top[x]]<depth[top[y]])
          swap(x,y);
        ress+=depth[x]-depth[top[x]]+1;
        x=fa[top[x]];
    }
    if(depth[x]>depth[y])
      swap(x,y);
    int ree=depth[y]-depth[x]+1;
    return ress+ree;
}

void zhuan(int x){ //转2进制
    int w=0;
    memset(shu,0,sizeof(shu));
    while(x!=0){
        shu[++w]=x%2;
        x/=2;
    }
    for(re int i=w;i>=1;i--)
      out(shu[i]);
    puts("");
}

int main(){
    in(n),in(m);
    FOR(i,1,m){
        in(x),in(y);
        add1(x,y);  //无向边
        add1(y,x); 
    }
    co=0;
    FOR(i,1,n)   //求环
      if(!dfn[i])
        tarjan(i,0);
    FOR(i,1,2*m){ //缩点重新建图
        if(i%2==0) continue;
        if(a[h1[i].ff]!=a[h1[i].to])
          add2(a[h1[i].ff],a[h1[i].to]),add2(a[h1[i].to],a[h1[i].ff]);
    }
    dfs1(1,0);
    dfs2(1,1);
    int kk,ansss;
    in(kk);
    FOR(i,1,kk){
        in(x),in(y);
        x=a[x],y=a[y];  //读入点所在的双连通分量的序号
        zhuan(qrange(x,y)); //转换2进制
    }
    return 0; //功德圆满
}