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

顾z

2018-10-12 11:52:50

Solution

# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/) ~~你没有发现两个字里的blog都不一样嘛~~ qwq 题目描述-->[p2783 有机化学之神偶尔会做作弊](https://www.luogu.org/problemnew/show/P2783) 挺恶心的一个题,涉及到了$tarjan+LCA$ 首先$Tarjan$缩点,对强连通分量之间建边.跑$LCA$即可 需要注意的是,求出来$LCA$之后求距离的时候,要$+1$ $$ans=dis[x]+dis[y]-2\times dis[lca]+1$$ 这里为为什么要加$1$?我们计算$dis[x]+dis[y]-2\times dis[lca]$的时候就减去了$LCA$这个点,需要再加上. (建议手绘一下 qwq) 转化为二进制也很简单,不多$BB$  ~~虽然刚开始我也写错了 qwq~~ **PS:当求$LCA$的时候要对$x,y$所在强连通分量求$LCA$** ``代码`` ```c++ /*变量名起的很玄学 qwq,看清*/ #include<bits/stdc++.h> #define N 100008 #define R register using namespace std; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int n,m,head[N],tot,dfn[N],low[N],stk[N],top,idx,h[N],ttt; struct code{int u,v;}edge[N<<3],e[N<<3]; int belong[N],col,dis[N],depth[N],f[N][21]; int q; bool inq[N]; inline void add(int x,int y) { e[++tot].u=h[x]; e[tot].v=y; h[x]=tot; } inline void ado(int x,int y) { edge[++ttt].u=head[x]; edge[ttt].v=y; head[x]=ttt; } void tarjan(int x,int fa) { dfn[x]=low[x]=++idx; stk[++top]=x;inq[x]=true; for(R int i=h[x];i;i=e[i].u) { if(e[i].v==fa)continue; if(!dfn[e[i].v]) { tarjan(e[i].v,x); low[x]=min(low[x],low[e[i].v]); } else if(inq[e[i].v]) low[x]=min(low[x],dfn[e[i].v]); } if(dfn[x]==low[x]) { col++; int now=-1; while(now!=x) { now=stk[top--]; inq[now]=false; belong[now]=col; } } } void dfs(int u,int fa) { f[u][0]=fa; dis[u]=dis[fa]+1; depth[u]=depth[fa]+1; for(R int i=1;(1<<i)<=depth[u];i++) f[u][i]=f[f[u][i-1]][i-1]; for(R int i=head[u];i;i=edge[i].u) { if(edge[i].v==fa)continue; dfs(edge[i].v,u); } } inline int lca(int x,int y) { int res=0; if(depth[x]>depth[y])swap(x,y); for(R int i=17;i>=0;i--) if(depth[x]+(1<<i)<=depth[y]) y=f[y][i]; if(x==y)return y; for(R int i=17;i>=0;i--) { if(f[x][i]==f[y][i])continue; x=f[x][i],y=f[y][i]; } return f[x][0]; } int main() { in(n),in(m); for(R int i=1,x,y;i<=m;i++) { in(x),in(y); add(x,y),add(y,x); } for(R int i=1;i<=n;i++) if(!dfn[i])tarjan(i,0); for(R int i=1;i<=n;i++) for(R int j=h[i];j;j=e[j].u) if(belong[i]!=belong[e[j].v]) ado(belong[i],belong[e[j].v]); dfs(belong[1],0); in(q); for(R int x,y,la;q;q--) { in(x),in(y); x = belong[x], y = belong[y]; la=lca(x,y); int ans=dis[x]+dis[y]-2*dis[la]+1; int size[15]={0},cnt=0; while(ans) { size[++cnt]=ans%2; ans/=2; } for(R int i=cnt;i>=1;i--) printf("%d",size[i]); putchar('\n'); } } ```