欢迎访问~原文出处——

---

---

题意概括

　　在一个森林里住着N(N<=10000)只猴子。在一开始，他们是互不认识的。但是随着时间的推移，猴子们少不了争斗，但那只会发生在互不认识(认识具有传递性)的两只猴子之间。争斗时，两只猴子都会请出他认识的猴子里最强壮的一只(有可能是他自己)进行争斗。争斗后，这两只猴子就互相认识。每个猴子有一个强壮值，但是被请出来的那两只猴子进行争斗后，他们的强壮值都会减半(例如10会减为5，5会减为2)。现给出每个猴子的初始强壮值，给出M次争斗，如果争斗的两只猴子不认识，那么输出争斗后两只猴子的认识的猴子里最强壮的猴子的强壮值，否则输出 -1。

---

 

题解

　　左偏树大力维护。

　　找根就最暴力的来。

---

 

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=100005;int n,m;int fa[N],ls[N],rs[N],npl[N],val[N];int getf(int k){	while (fa[k])		k=fa[k];	return k;}int merge(int a,int b){	if (!a||!b)		return a+b;	if (val[a]
          
           npl[ls[a]]) swap(rs[a],ls[a]); npl[a]=npl[rs[a]]+1; return a;}int weaken(int a){ fa[ls[a]]=fa[rs[a]]=0; int b=merge(ls[a],rs[a]); fa[a]=ls[a]=rs[a]=npl[a]=0; val[a]>>=1; return merge(a,b);} int main(){ while (~scanf("%d",&n)){ for (int i=1;i<=n;i++){ scanf("%d",&val[i]); fa[i]=ls[i]=rs[i]=npl[i]=0; } scanf("%d",&m); while (m--){ int a,b; scanf("%d%d",&a,&b); a=getf(a),b=getf(b); if (a==b){ puts("-1"); continue; } a=weaken(a); b=weaken(b); printf("%d\n",max(val[a],val[b])); merge(a,b); } } return 0;}