云剪贴板 6f9qehr7

# 板子 ```cpp #include<bits/stdc++.h> using namespace std; const int N=1e5+50,P=1e9+7; int read() {int x=0;short f=1;char s=getchar();while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}return x*f;} void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;} int n,m,val[N],ls[N],rs[N],x,y,dis[N],fa[N]; char opt; int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } 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); if(dis[ls[x]]<dis[rs[x]]) swap(rs[x],ls[x]); dis[x]=dis[rs[x]]+1; fa[ls[x]]=fa[rs[x]]=fa[x]=x; return x; } void solve(int l,int r) { val[l]/=2,val[r]/=2; int rt=fa[ls[l]]=fa[rs[l]]=fa[ls[r]]=fa[rs[r]]=merge(merge(ls[l],rs[l]),merge(ls[r],rs[r])); ls[l]=rs[l]=ls[r]=rs[r]=0; rt=fa[l]=fa[r]=merge(merge(l,r),rt); write(val[fa[l]]);puts(""); } signed main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) val[i]=read(),fa[i]=i,dis[i]=ls[i]=rs[i]=0; m=read(); for(int i=1;i<=m;i++) { x=read(),y=read(); int l=find(x),r=find(y); if(l==r) puts("-1"); else solve(l,r); } } return 0; } ```