题解 P2783 【有机化学之神偶尔会做作弊】
Juan_feng
2018-09-09 08:07:56
### 终于有机会写一道黑题~~至少目前是这样~~的题解了！小蒟蒻好兴奋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; //功德圆满
}
```