参考:http://blog.csdn.net/pi9nc/article/details/11827501
题目:https://vjudge.net/problem/HDU-1512

他的注释很详细.

题目大意：有n个猴子，一开始每个猴子只认识自己。每个猴子有一个力量值，力量值越大表示这个猴子打架越厉害。如果2个猴子不认识，他们就会找他们认识的猴子中力量最大的出来单挑，单挑不论输赢，单挑的2个猴子力量值减半，这2拨猴子就都认识了，不打不相识嘛。现在给m组询问，如果2只猴子相互认识，输出-1，否则他们各自找自己认识的最牛叉的猴子单挑，求挑完后这拨猴子力量最大值。

#include<bits/stdc++.h>using namespace std;
#define MP make_pair
#define N 100005
#define LL long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define md ((ll+rr)>>1)
#define ls (i<<1)
#define rs ((i<<1)|1)
#define lson ls,ll,md
#define rson rs,md+1,rrint n,m;
int fa[N];
int a[N];
int l[N],r[N],v[N],d[N];
int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);
}int merge(int x,int y){if(!x)return y;if(!y)return x;if(v[x]<v[y])swap(x,y);//大根堆r[x]=merge(r[x],y);fa[r[x]]=x;//并查集的部分if(d[l[x]]<d[r[x]])swap(l[x],r[x]);d[x]=d[r[x]]+1;return x;
}
int pop(int x){fa[l[x]]=l[x];fa[r[x]]=r[x];//先把左儿子设自己为跟,右儿子也是int ll=l[x],rr=r[x];l[x]=r[x]=d[x]=0;//printf("%d %d\n",ll,rr);return merge(ll,rr);
}
int tot;
void Init(int x){tot++;v[tot]=x;l[tot]=r[tot]=d[tot]=0;
}
int main(){while(~scanf("%d",&n)){tot=0;for(int i=1;i<=n;++i){scanf("%d",&a[i]);fa[i]=i;Init(a[i]);}scanf("%d",&m);for(int i=1;i<=m;++i){int x,y;scanf("%d%d",&x,&y);int fx=Find(x),fy=Find(y);if(fx==fy)puts("-1");else{int tmpx=pop(fx);//先把最小的取出来v[fx]/=2;fx=merge(tmpx,fx);//再合并回去.找到合适的位置插入,这样就不会违反堆 的性质int tmpy=pop(fy);v[fy]/=2;fy=merge(tmpy,fy);printf("%d\n",v[merge(fx,fy)]);}}}
}