meaning of the title

There are n monkeys who don't know each other at first. Every time two monkeys want to fight, they will find the most powerful monkeys they know to help them fight (but they go to the theatre). After the fight, the force value of the fighting monkeys (not the ones watching the theatre) will be reduced by half (next pick up), and they also know each other. At this time, they will ask the most powerful monkeys they know about the martial arts. Force value, the fight before the recognition of output-1.

n,m<=100000

Title Solution

It's good to use it directly and stack it together. To finish the battle is to merge two teams, but how to reduce the force value?

Just kick the boss out and start over again. The specific implementation is to merge the boss's ls and rs, so that he comes out, and then merge his and LS (rs) heap.

There are some details in the implementation, which are implemented in the code.

#include<bits/stdc++.h>
using namespace std;

const int maxn=100005;
int n,m,a[maxn];
int fa[maxn],ls[maxn],rs[maxn],dis[maxn],val[maxn];

int find(int x){
  return fa[x]==x ? x : find(fa[x]);
}

int merge(int A,int B){
  if(!A) return B;
  if(!B) return A;
  if(val[A]<val[B]) swap(A,B);
  rs[A]=merge(rs[A],B);
  fa[rs[A]]=A;
  if(dis[rs[A]]>dis[ls[A]]) swap(rs[A],ls[A]);
  if(!rs[A]) dis[A]=0;
  else dis[A]=dis[rs[A]]+1;
  return A;
}

int pop(int x){//int Because it doesn't change ls,rs Merger x Maybe he's a leaf node, he'll be RE
  fa[ls[x]]=ls[x];
  fa[rs[x]]=rs[x];
  fa[x]=x;
  int ret=merge(ls[x],rs[x]);
  ls[x]=rs[x]=0;//Find out the above before you can change it.
  return ret;
}

int main(){
  //freopen("testdata.in","r",stdin);
  while(scanf("%d",&n)!=EOF){
    for(int i=1;i<=n;i++){
      scanf("%d",&val[i]);
      fa[i]=i;
      ls[i]=rs[i]=dis[i]=0;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
      int x,y;
      scanf("%d%d",&x,&y);
      int dx=find(x),dy=find(y);
      if(dx==dy){printf("-1\n");continue;}
      //printf("*--------%d %d------------*\n",dx,dy);
      int xx=pop(dx),yy=pop(dy);
      //printf("*---------%d %d------*\n",xx,yy);
      val[dx]>>=1;
      val[dy]>>=1;
      merge(dx,find(xx));
      merge(dy,find(yy));
      merge(find(dx),find(dy));
      //for(int j=1;j<=n;j++) printf("%d ",fa[j]);
      //putchar(10);
      printf("%d\n",val[find(dx)]);
    }
  }
  return 0;
}