http://acm.hdu.edu.cn/showproblem.php?pid=1512
题意：
有n只猴子，每只猴子一开始有个力量值，并且互相不认识，现有每次有两只猴子要决斗，如果认识，就不打了，否则的话，这两只都会从它们所认识的猴子中派出一只力量值最大的猴子出来，并且这只猴子的力量值会减半，在打过之后，这两只猴子所在的集体就都认识了。
思路：
这是一道左偏树的模板题。
每个节点有5个值，l为左儿子节点，r为右儿子节点，fa为父亲节点（父亲节点的用法与并查集相似），val为优先级（这道题目就是大根堆），dis是距离值（在两棵树合并的时候使用，根据dis来决定左右子树是否需要对换）。
一开始每只猴子就是一棵树，每次决斗就是将两棵树进行合并。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = +; int n, m; struct Heap
{
int l,r,fa,val,dis;
}t[maxn]; int finds(int x)
{
return t[x].fa == -? x:t[x].fa = finds(t[x].fa);
} int merge(int x, int y)
{
if(x == ) return y; //如果为0的话，就说明是空子树，根节点当然就是另一节点了
if(y == ) return x;
if(t[y].val>t[x].val) swap(x,y); //始终往右子树进行插入
t[x].r = merge(t[x].r,y);
t[t[x].r].fa = x;
if(t[t[x].l].dis < t[t[x].r].dis) swap(t[x].l,t[x].r); //是否需要左右子树的对换，这样是为了右子树尽量短
if(t[x].r == ) t[x].dis = ; //距离的重新分配
else t[x].dis = t[t[x].r].dis + ;
return x;
} int pop(int &root)
{
int l = t[root].l;
int r = t[root].r;
t[root].l = t[root].r = t[root].dis = ;
t[root].fa = -;
t[l].fa = t[r].fa = -; //删除root根节点
return merge(l,r); //这样一来相当于分裂成了两棵子树，重新进行合并，最后返回值为合并后的根节点
} int push(int x, int y)
{
return merge(x,y);
} int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%d",&n))
{
for(int i=;i<=n;i++)
{
t[i].l=t[i].r=t[i].dis=;
t[i].fa=-;
scanf("%d",&t[i].val);
}
scanf("%d",&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
int x=finds(a);
int y=finds(b);
if(x!=y)
{
t[x].val/=;
int xx = push( pop(x),x);
t[y].val/=;
int yy = push( pop(y),y);
printf("%d\n",t[merge(xx,yy)].val);
}
else puts("-1");
}
}
return ;
}