我的AC代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,dis[N],f[N],ls[N],rs[N],val[N];
int merge(int x,int y){
if(!x||!y) return x+y;
if(val[x]<val[y]) swap(x,y);
rs[x]=merge(rs[x],y);
f[rs[x]]=x;
if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
dis[x]=dis[ls[x]]+1;
return x;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int weak(int x){
val[x]>>=1;
int fa=merge(ls[x],rs[x]);
ls[x]=rs[x]=dis[x]=0;
return f[fa]=f[x]=merge(fa,x);
}
int main(){
while(scanf("%d",&n)==1){
dis[0]=-1;
for(register int i=1;i<=n;i++){
f[i]=i;
ls[i]=rs[i]=dis[i]=0;
scanf("%d",&val[i]);
}
scanf("%d",&m);
for(register int i=1,x,y;i<=m;i++){
scanf("%d %d",&x,&y);
int f1=find(x),f2=find(y);
if(f1==f2) printf("-1\n");
else{
int l=weak(f1),r=weak(f2);
f[l]=f[r]=merge(l,r);
printf("%d\n",val[f[l]]);
}
}
}
}
```
by BMTXLRC @ 2021-07-03 21:48:22